EQUIPASS  Equivalent Passwords
Yesterday you arrived at the hotel, and you kept all your valuable stuff in your room's safe. Unfortunately, you forgot the password. But you have a very long list of passwords (each password is at most 5 digits), and you are sure that your password is one of them.
The safe will consider some passwords equivalent. Two passwords A and B are considered equivalent, if they are of the same length, and A[i]  B[i] is the same for all possible values of i, where X[i] is the ith digit of X and Y is the absolute value of Y.
You will go through the list of passwords in the given order. For each password, you will do the following:
If the same password or any of its equivalent passwords were typed before, skip this password.
Otherwise, type this password into the safe.
If it's the correct password (or any of its equivalent passwords), the safe will open and you will stop any further processing.
Now given the list of all passwords, you would like to know, in the worst case scenario, what is the maximum number of passwords you will have to type?
Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T (1 ≤ T ≤ 50) representing the number of test cases. Followed by T test cases. Each test case starts with a line will containing an integer N (1 ≤ N ≤ 100,000) representing the number of passwords, followed by N lines, each one will contain a nonempty string of at most 5 digits (from '0' to '9'), representing a password (might contain leading zeros).
Output Format:
For each test case print a single line containing "Case n:" (without quotes) where n is the test case number (starting from 1) followed by a space then the maximum number of passwords you will have to type.
Sample Input:
3 3000 111 222 4 1111 123 214 2222 3 43434 54545 45454
Sample Output:
Case 1: 1 Case 2: 2 Case 3: 2
Notes:
In the first test case: all passwords are equivalent to each other. This means that the first password will open the safe for sure.
In the second test case:
 If the first password is the correct one, you will type 1 password.
 If the second password is the correct one, you will type 2 passwords.
 If the third password is the correct one, you will type 2 passwords (because the second password is equivalent to the third one).
 If the fourth password is the correct one, you will type 1 password (because the first password is equivalent to the fourth one).
In the third test case:
 If the first password is the correct one, you will type 1 password.
 If the second password is the correct one, you will type 1 password (because the first password is equivalent to the second one).
 If the third password is the correct one, you will type 2 passwords. Even though the third password is equivalent to the second password, the second password was skipped, and therefore you should type the third password.
hide comments
preet_t:
20181206 17:11:04
@Tensor can you tell what's wrong in my submission, id: 22833964 

રચિત (Rachit):
20150810 15:17:11
Last rank on this problem with 14.26s time! Guess I should improve my algo quite a lot... :D


nadal17:
20150710 13:41:35
Is an O(c*n) algorithm with c = 50*2^5 effective enough for this problem? Such algorithm with Java is giving TLE atm. Guess this requires constant factor optimization... Last edit: 20150710 13:42:44 

abdelkarim:
20150529 03:09:48
why "All except: SCM chicken" are you kidding me ?!


gamer496:
20150318 04:04:26
@Tensor could you tell what's wrong with this code submission_id 13886002


MaHmOuD.:
20150309 11:42:33
@Tensor, Could you give me another test case after checking what's wrong with my code (13814725) , please?

Added by:  Tensor 
Date:  20150308 
Time limit:  5s15s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 
Resource:  ACPC 2014 