题目内容

某工厂有 $n$ 件产品，每件产品分配了一个恰好由 $6$ 个数字组成的序列号（可含前导 $0$）。

为了简化记录，管理员决定进行一次批量调整：选择一个位置 $pos$（$pos$ 为 $1$ 到 $6$ 的整数）和一个数字 $d$（$0 \le d \le 9$），将所有产品序列号在第 $pos$ 位上的数字全部改为 $d$。

请问，通过一次这样的调整，能够使不同序列号的种类数最少是多少？

数据范围与约束

• 测试数据组数 $T$ 满足 $1 \le T \le 10^5$。
• 每组数据中产品个数 $n$ 满足 $1 \le n \le 10^5$。
• 所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。
• 每个序列号均为长度恰好为 $6$ 的数字字符串，仅包含字符 0 到 9。

输入描述

第一行包含一个整数 $T$，表示测试数据的组数。 接下来依次描述每组数据。对于每组数据： 第一行包含一个整数 $n$，表示产品个数。 第二行包含 $n$ 个由空格分隔的长度为 $6$ 的数字字符串，依次表示各产品的原始序列号。

输出描述

对于每组数据，输出一行一个整数，表示进行一次统一调整后，不同序列号的最少种类数。

样例1

输入

2
1
123456
3
111111 111112 111122

输出

1
2

说明

第一组数据中产品数量为 1，无论如何修改，最终不同序列号的种类数均为 1。

第二组数据中有 3 件产品，原始序列号为 111111、111112、111122。如果选择修改第 6 位（$pos=6$），删除该位后得到的 5 位串分别为 11111、11111、11112，只有 2 种；若修改其他位置，不同串的种类数均不少于 2。因此最少种类数为 2。

样例2

输入

1
4
000000 010000 020000 030000

输出

1

说明

所有产品的序列号仅在第 2 位（$pos=2$）上不同，其余 5 位完全一致。选择修改第 2 位并将该位统一改为任意数字（例如 0），相当于删除该位，所有产品对应的 5 位串都变为 00000。因此不同种类数可减少到 1。

样例3

输入

1
4
111111 211111 222222 322222

输出

2

说明

选择修改第 1 位（$pos=1$）。删除第 1 位后，前两个产品的 5 位串均为 11111，后两个产品的 5 位串均为 22222，此时种类数为 2。若尝试修改其他位置，种类数均不小于 2。因此最少为 2。