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