Informatics 1

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

De Universal Product Code (UPC) is een streepjescode waarbij twaalf cijfers volgens een bepaalde methode worden voorgesteld als verticale strepen. In de Verenigde Staten wordt UPC algemeen gebruikt om de producten in een winkel van een unieke code te voorzien. Op die manier kunnen kassa-afhandeling en voorraadadministratie grotendeels geautomatiseerd worden. Buiten de VS wordt UPC nauwelijks gebruikt. In plaats daarvan gebruikt men EAN-13, een uitbreiding op UPC voor internationaal gebruik.

Elke UPC streepjescode bestaat uit een opeenvolging van zwarte lijnen en witte ruimtes boven een reeks van 12 cijfers. Letters of andere karakters kunnen niet met UPC gecodeerd worden. Er bestaat een één-op-één verband tussen de cijfers en hun grafische voorstelling. Met andere woorden, er is maar één manier om een getal van 12 cijfers visueel voor te stellen en er is maar één manier om een grafische streepjescode te decoderen als een getal van 12 cijfers.

Het eerste cijfer van UPC wordt de prefix genoemd. Deze prefix geeft het soort product aan waarvoor de code staat. De prefix wordt gevolgd door twee groepen van vijf cijfers. Het laatste cijfer is een controlecijfer dat toelaat om fouten te detecteren. Het controlecijfer wordt berekend aan de hand van de eerste elf cijfers van UPC. Een barcodelezer rekent het controlecijfer na, en controleert of dit hetzelfde is als het controlecijfer in de barcode zelf. Als de twee controlecijfers verschillend zijn, dan wordt de code niet aanvaard.

Het controlecijfer $d_1$ van de UPC barcode $d_{12}d_{11}d_{10}d_{9}d_8d_7d_6d_5d_4d_3d_2d_1$ wordt berekend zodat de volgende som een veelvoud van 10 oplevert: \[ 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}) \] Om het controlecijfer te bepalen moet men met andere woorden eerst de som bepalen van de eerste 11 cijfers op de oneven posities (het eerste cijfer, het derde cijfer,…) en deze som met drie vermendigvuldigen. Hierbij wordt de som van de eerste 11 cijfers op de even posities opgeteld (het tweede cijfer, het vierde cijfer,…). Van dit resultaat bepaalt men de rest na deling door tien. Als de rest verschillend is van nul, dan trekken we deze rest af van 10 om het controlecijfer te bekomen. Anders is het controlecijfer gelijk aan nul.

Het controlecijfer dat correspondeert met de gedeeltelijke UPC barcode 0-48500-00102 (Tropicana Pure Premium Orange Juice) is bijvoorbeeld gelijk aan 8 omdat \[ \mathbf{8} + 0 + 0 + 0 + 5 + 4 + 3 \times (2 + 1 + 0 + 0 + 8 + 0) = 50 \] en 50 een veelvoud van 10 is.

Invoer

De invoer bestaat uit $t$ gedeeltelijke UPC barcodes. De eerste regel van de invoer bevat een getal $t$ dat aangeeft hoeveel barcodes er volgen. Daarna volgen de $t$ barcodes, elk op een afzonderlijke regel. Elke barcode bestaat uit een reeks van 11 cijfers, waarvan het controlecijfer (het twaalfde cijfer) ontbreekt.

Uitvoer

Schrijf voor elke van de gedeeltelijke UPC barcode uit de invoer de volledige UPC barcode (dus de gedeeltelijke barcode aangevuld met het controlecijfer) uit. Zorg ervoor dat er geen overbodige herhaling van broncode voorkomt in je oplossing.

Voorbeeld

Invoer:

5
03600029145
01234567890
81113800020
01600066060
08004744069

Uitvoer:

036000291452
012345678905
811138000202
016000660601
080047440694