Codejamon 游戏火了！全世界的粉丝都在预测并押注哪支队伍会获胜。

一家博彩公司为所有队伍提供了赔率；第 $i$ 支队伍的赔率为 $A_i:B_i$。对于每支队伍，你可以押注任意正数金额，且不必在每支队伍上押注相同的金额。如果第 $i$ 支队伍获胜，你将收回你在该队上的押注，并额外获得 $\frac{B_i}{A_i} \times (\text{你在该队上的押注})$。

例如，假设有两支队伍，赔率分别为 $5:3$ 和 $2:7$，你在第一支队伍上押注 $20$ 美元，在第二支队伍上押注 $10$ 美元。如果第一支队伍获胜，你将输掉在第二支队伍上的 $10$ 美元押注，但你会收回 $20$ 美元的押注，并额外获得 $\frac{3}{5} \times 20 = 12$ 美元，最终总共得到 $32$ 美元。如果第二支队伍获胜，你将输掉在第一支队伍上的 $20$ 美元押注，但你会收回 $10$ 美元的押注，并额外获得 $\frac{7}{2} \times 10 = 35$ 美元，最终总共得到 $45$ 美元。无论哪种情况，你最终得到的钱都比你押注的总额（$20+10=30$ 美元）要多。

作为一个贪心的粉丝，你希望尽可能多地押注不同的队伍，以确保只要其中一支队伍获胜，你最终得到的钱总比你押注的总额多。你能算出最多可以押注多少支队伍吗？

输入格式

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

每个测试用例的第一行包含一个整数 $N$，表示游戏中的队伍数量。

接下来有 $N$ 行，每行是一个形如 $A_i:B_i$ 的数字对（即一个数字 $A_i$，后跟一个冒号，再跟一个数字 $B_i$，中间没有空格），表示第 $i$ 支队伍的赔率。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在题目规定的条件下，你可以押注的队伍的最大数量。

数据范围

• $1 \le T \le 100$
• $1 \le N \le 100$
• $0 < A_i, B_i < 100$
• $A_i$ 和 $B_i$ 小数点后最多有 $3$ 位数字。

样例

样例输入 1

1
3
1:1.1
1:0.2
1.5:1.7

样例输出 1

Case #1: 2

说明

在样例 #1 中，一种最优策略是在第一支队伍上押注 $1.5$ 美元，在第三支队伍上押注 $1.5$ 美元。如果第一支队伍获胜，你将收回 $1.5 + 1.5 \times (1.1/1) = 3.15$ 美元；如果第三支队伍获胜，你将收回 $1.5 + (1.7/1.5) \times 1.5 = 3.2$ 美元。这两种情况下的收益都高于你押注的总金额（$1.5 + 1.5 = 3$ 美元）。

然而，无法同时押注所有三支队伍并保证盈利。