你要举办一场派对。为了准备派对，你需要混合三种不同类型的果汁：苹果汁（Apple）、香蕉汁（Banana）和胡萝卜汁（Carrot）来制作饮料。我们将这些果汁分别命名为 A、B 和 C。

你需要决定每种果汁在饮料中所占的比例，使得参加派对的人中喜欢这种饮料的人数尽可能多。

每个人对这 3 种果汁都有一个最低比例要求。只有当饮料中这 3 种果汁的比例均大于或等于他们各自的最低比例要求时，他们才会喜欢这种饮料。

请确定你能满足的最大人数。

输入格式

输入文件包含一行整数 $T$，表示测试用例的数量。

对于每个测试用例： 一行包含整数 $N$，表示参加派对的人数。 $N$ 行，每行包含三个用空格分隔的数字 "A B C"，表示该人对每种果汁的最低比例要求。$A, B, C$ 是 $0$ 到 $10000$ 之间的整数，表示万分之几的比例。满足 $A + B + C \le 10000$。

输出格式

输出 $T$ 行，每行对应输入文件中相应顺序的测试用例，格式为 "Case #X: Y"，其中 $X$ 是测试用例的编号（从 1 开始），$Y$ 是你能满足的最大人数。

样例

输入格式 1

3
3
10000 0 0
0 10000 0
0 0 10000
3
5000 0 0
0 2000 0
0 0 4000
5
0 1250 0
3000 0 3000
1000 1000 1000
2000 1000 2000
1000 3000 2000

输出格式 1

Case #1: 1
Case #2: 2
Case #3: 5

说明

在第一个样例中，对于每种果汁，都有一个人希望饮料完全由该种果汁制成！显然，我们只能满足其中一个人。

在第二个样例中，我们可以满足三个人中任意两个人的偏好。

在第三个样例中，如果我们按等比例（各占三分之一）混合这三种果汁，所有五个人都会喜欢这种饮料。