동등한 비밀번호

어제 호텔에 도착해서 귀중품을 객실 금고에 넣어 두었다. 그런데 비밀번호를 잊어버렸다. 대신 비밀번호 후보를 아주 길게 적어 둔 목록이 있고, 후보는 모두 길이가 5 이하인 숫자 문자열이다. 진짜 비밀번호는 이 목록 안에 반드시 있다.

금고는 어떤 비밀번호끼리를 같은 것으로 취급한다. 두 비밀번호 $A$와 $B$는 길이가 같고 모든 위치 $i$에서 $|A_i - B_i|$가 하나의 값으로 일정할 때 동등하다. 여기서 $X_i$는 $X$의 $i$번째 자리 숫자다.

목록을 주어진 순서대로 훑으면서 비밀번호마다 다음을 한다.

1. 그 비밀번호나 그와 동등한 비밀번호를 앞에서 이미 입력했다면 건너뛴다.
2. 그렇지 않으면 금고에 입력한다.
3. 입력한 비밀번호가 진짜 비밀번호이거나 진짜 비밀번호와 동등하면 금고가 열리고, 거기서 멈춘다.

목록이 주어질 때 최악의 경우 입력하게 되는 비밀번호 개수의 최댓값을 구하라.

첫 줄에 테스트 케이스 개수 $T$ ($1 \le T \le 50$)가 주어진다. 각 테스트 케이스의 첫 줄에는 비밀번호 개수 $N$ ($1 \le N \le 100000$)이 주어지고, 이어지는 $N$개 줄에 비밀번호가 한 줄에 하나씩 주어진다. 비밀번호는 '0'부터 '9'까지의 숫자로만 이루어진 길이 1 이상 5 이하의 문자열이며, 앞자리가 0일 수도 있다.

각 테스트 케이스마다 Case n: x 형식으로 한 줄씩 출력한다. $n$은 1부터 시작하는 테스트 케이스 번호이고, $x$는 최악의 경우 입력하게 되는 비밀번호 개수의 최댓값이다.

첫 번째 예제의 첫 테스트 케이스에서 비밀번호는 000, 111, 222이고 셋은 서로 동등하다. 그래서 첫 비밀번호 하나로 금고가 열린다.

두 번째 테스트 케이스의 비밀번호는 1111, 123, 214, 2222이다.

• 1111이 진짜 비밀번호라면 1개를 입력한다.
• 123이 진짜 비밀번호라면 2개를 입력한다.
• 214가 진짜 비밀번호라면 2개를 입력한다. 214는 123과 동등하기 때문이다.
• 2222가 진짜 비밀번호라면 1개를 입력한다. 2222는 1111과 동등하기 때문이다.

세 번째 테스트 케이스의 비밀번호는 43434, 54545, 45454이다.

• 43434가 진짜 비밀번호라면 1개를 입력한다.
• 54545가 진짜 비밀번호라면 1개를 입력한다. 54545는 43434와 동등하기 때문이다.
• 45454가 진짜 비밀번호라면 2개를 입력한다. 45454는 54545와 동등하지만 54545를 건너뛰었으므로 45454는 직접 입력해야 한다.