昨天你到达了酒店，并将所有贵重物品存放在房间的保险柜里。不幸的是，你忘记了密码。但你有一份很长的密码列表（每个密码最多 5 位数字），并且你确信你的密码就在其中。

保险柜会将某些密码视为等价的。如果两个密码 $A$ 和 $B$ 长度相同，且对于所有可能的 $i$，都有 $|A[i] - B[i]|$ 相等，则称这两个密码等价，其中 $X[i]$ 表示 $X$ 的第 $i$ 位数字。

你将按照给定的顺序遍历密码列表。对于每个密码，你将执行以下操作：

1. 如果之前已经输入过相同的密码或任何与它等价的密码，则跳过该密码。
2. 否则，将此密码输入保险柜。
3. 如果这是正确的密码（或任何与它等价的密码），保险柜将打开，你将停止后续处理。

现在给定所有密码的列表，你想知道在最坏情况下，你最多需要输入多少个密码？

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$ ($1 \le T \le 50$)，表示测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$ ($1 \le N \le 100,000$)，表示密码的数量，随后是 $N$ 行，每行包含一个最多 5 位数字（从 ‘0’ 到 ‘9’）的非空字符串，代表一个密码（可能包含前导零）。

输出格式

对于每个测试用例，打印一行包含 “Case n:”（不含引号），其中 $n$ 是测试用例编号（从 1 开始），后跟一个空格，然后是你在最坏情况下需要输入的密码的最大数量。

样例

输入 1

3
3
000
111
222
4
1111
123
214
2222
3
43434
54545
45454

输出 1

Case 1: 1
Case 2: 2
Case 3: 2

说明

在第一个测试用例中：所有密码彼此等价。这意味着第一个密码肯定能打开保险柜。

在第二个测试用例中：

• 如果第一个密码是正确的，你将输入 1 个密码。
• 如果第二个密码是正确的，你将输入 2 个密码。
• 如果第三个密码是正确的，你将输入 2 个密码（因为第二个密码与第三个密码等价）。
• 如果第四个密码是正确的，你将输入 1 个密码（因为第一个密码与第四个密码等价）。

在第三个测试用例中：

• 如果第一个密码是正确的，你将输入 1 个密码。
• 如果第二个密码是正确的，你将输入 1 个密码（因为第一个密码与第二个密码等价）。
• 如果第三个密码是正确的，你将输入 2 个密码。尽管第三个密码与第二个密码等价，但第二个密码已被跳过，因此你应该输入第三个密码。