Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3485
Identification Number

Time Limit: 3 Seconds      Memory Limit: 65536 KB      Special Judge

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.

Number system for the first generation identity card
1 2 3 4 5 6 Y Y M M D D 8 8 8
Address code Date of Birth Order code
Number system for the second generation identity card
1 2 3 4 5 6 Y Y Y Y M M D D 8 8 8 X
Address code Date of Birth Order code Checksum

The identification number must obey the following constraints:

  1. The address code refers to the resident's location. For simplicity, here we consider any digits are legal.
  2. The Date of Birth must be a legal date. Since the robbery happened last night, we assume any date from Jan 1, 1900 to Apr 2, 2011 (inclusive) is legal, and others are illegal. For identification number in first generation card, the first 2 digits of year are omitted, and the date is considered legal if one of the two interpretations (19xx or 20xx) is legal.
  3. Order code is the code used to disambiguate people with the same date of birth and address code. We consider any digits are legal.
  4. Checksum confirms the validity of the ID number from the first 17 digits in second generation identity card. It is calculated by:
    1. Mark the identification code right-to-left a1, a2, ... , a18. a1 is the checksum digit.
    2. Calculate coefficient for each digit: Wi = 2i - 1 mod 11. For simplicity, Wi is given in the following table:
      i 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
      Wi 7 9 10 5 8 4 2 1 6 3 7 9 10 5 8 4 2 1
    3. Calculation of S = \sum_{i=2}^{18} a_i * W_i
    4. a1 = (12 - (S mod 11)) mod 11
    5. If a1 is between 0 and 9, the checksum code is a1 itself. If a1 is 10, the checksum code is "X" (upper case).

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.

Input

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.

Output

For each test case, you need to output the correct identification number described above. If there are multiple solutions, any one is OK.

Sample Input

2
111111111111111111
111111111111111

Sample Output

111111191110111111
111111111111111

Author: LI, Cheng
Contest: The 11th Zhejiang University Programming Contest
Submit    Status