在这题中：

Description

对于二进制串a，b，他们之间的海明距离是指两个串异或之后串中1的个数。异或的规则为：

0 XOR 0 = 0

1 XOR 0 = 1

0 XOR 1 = 1

1 XOR 1 = 0

计算两个串之间的海明距离的时候，他们的长度必须相同。现在我们给出N个不同的二进制串，请计算出这些串两两之间的最短海明距离。

Input

第一个数字是整数T（T≤10），代表数据的组数。

接下来有T组数据，每组数据的第一行是一个正整数N，代表不同的二进制串的个数。接下来是N行，每行都是一个二进制串(长度是5)。我们用数字(0-9)和字符(A-F)来表示这个二进制串。它代表这个二进制串的16进制码。例如，“12345”代表的二进制串为“00010010001101000101”。

Output

对于每个数据，请输出一个整数，即答案值。

Sample Input

2
2
12345
54321
4
12345
6789A
BCDEF
0137F

Sample Output

6
7

Data Constraint

对于30%的数据有1≤N≤100

对于全部数据，有1≤N≤100000

有个人提出了一种做法并ac了，就是把这个二进制串排序后取相邻的海明距离并取最小值。但是这样明显是错误的，所以把二进制的第一位移动到最后一位之后再拍一次序，再取相邻的海明距离的最小值，以此类推。但是我证明不出来这是正确的，求各位dalao证明一下。