|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||256 MB||19||7||7||43.750%|
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 i-th 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:
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?
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 non-empty string of at most 5 digits (from ‘0’ to ‘9’), representing a password (might contain leading zeros).
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.
3 3 000 111 222 4 1111 123 214 2222 3 43434 54545 45454
Case 1: 1 Case 2: 2 Case 3: 2
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:
In the third test case: