The Universal Product Code (UPC) is a bar code where twelve numbers are set up in a certain way as vertical lines. In the United States, UPC is used to provide products in a shop with a unique code. That way, cash register handling and stock administration can be mostly automated. Outside the US, UPC is barely used. Instead, EAN-13¹, which is an expansion of UPC for international use, is used.

Every UPC bar code consists of a sequence of black and white lines above a series of 12 numbers. Letters or other characters can't be coded with UPC. There is a one on one connection between the numbers and their graphic representation. In other words, there is only one way to represent a number of 12 digits as a bar code and there is only one way to represent a bar code as a number of 12 digits.

The first digit of UPC is called the prefix. This prefix indicates the kind of product and what it stands for. The prefix proceeds two groups of 5 digits each. The last digit is a check digit that allows detection of mistakes. The check digit is calculated on the basis of the first 11 digits of UPC. A bar code reader calculates the check digit and checks if this is the same check digit as in the bar code. If the two check digits differ, the code is not accepted.

The check digit $$d_1$$ of the UPC bar code $$d_{12}d_{11}d_{10}d_{9}d_8d_7d_6d_5d_4d_3d_2d_1$$ is calculated so that the next sum is a multiple of 10: \[ d_1 + d_3 + d_5 + d_7 + d_9 + d_{11} + 3 \times (d_2 + d_4 + d_6 + d_8 + d_{10} + d_{12}) \] This means that, to determine the check digit, you first have to determine the sum of the first 11 digits summed up on the uneven positions (the first digit, the third digit,…) and multiply this sum by three. Here, the sum of the first 11 digits on the even positions is made (the second digit, the forth digit, …). The rest of this result is determined by dividing the outcome by 10. If the rest doesn't equal zero, we subtract it from 10 to determine the check digit. Otherwise, the check digit equals zero.

The check digit that corresponds with the partial UPC bar code 0-48500-00102 (Tropicana Pure Premium Orange Juice), for example, is 8 because \[ \mathbf{8} + 0 + 0 + 0 + 5 + 4 + 3 \times (2 + 1 + 0 + 0 + 8 + 0) = 50 \] and 50 are a multiple of 10.

Input

The input consists of $$t$$ partial UPC bar codes. The first line of the input contains a number $$t$$ that indicates how many bar codes follow. After that, the $$t$$ bar codes follow, each on a separate line. Every bar code consists of a sequence of 11 digits, of which the check digit (the 12th digit) is missing.

Output

Print the entire UPC bar code (i.e. the partial bar code plus the check digit) for every partial UPC bar code from the input. Make sure there is no unnecessary repetition of source code in your solution.

Example

Input:

5
03600029145
01234567890
81113800020
01600066060
08004744069

Output:

036000291452
012345678905
811138000202
016000660601
080047440694