104 - The 11th Zhejiang University Programming Contest - I
Mr. Wu, the inspector of the district, is really angry for a robbery happened last night. The robber escaped while Mr. Wu knows nothing about him. The only clue Mr. Wu has is a photo of the robber, which is recorded by the security camera.
Fortunately, the robber was seen by a witness in a train station, and his identity card was captured on a video camera when he was passing security check. As you know, each identity card in China has a unique identification number. Therefore Mr. Wu can easily find who the robber is by looking up the ID in computer database. But he failed, and found the number was not in the database. He guesses some digits in the identification number are misinterpreted because the picture of the robber's identity card is in bad quality.
To find the original identification number, Mr. Wu assumes that only a minimal number of characters are misinterpreted. While this assumption may be reasonable, he finds it hard for him to determine the correct number. So he turns you, a talented programmer, to help him find the correct answer.
To accomplish this task, you need to have some basic knowledge about identity cards used in China. There are two number system used for identification number, namely the first generation and the second generation. The first generation consists of a 15-digit code while the second generation consists of an 18-digit code. See following tables for details.
The identification number must obey the following constraints:
Now given an identification number either in 15-digit format or 18-digit format, you need to output a legal identification number by changing minimal number of digits in original one.
There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases.
Each test case consists of a line of identification number, in either 15-digit format or in 18-digit format. All characters are digits except the last character in an 18-digit-format code may be a capital 'X'. There will be no extra characters.
For each test case, you need to output the correct identification number described above. If there are multiple solutions, any one is OK.
2 111111111111111111 111111111111111
Author: Local Contests 2011 Committee
Contest: The 11th Zhejiang University Programming Contest