Problem D

Start

Källkod: start.pas, start.p eller start.c
Femtonspelet är ett klassiskt spel som de flesta säkerligen stött på i någon form. Spelet består av ett bräde med 16 rutor innehållande 15 brickor. Brädets 16 rutor är uppdelade i 4 rader och 4 kolonner. Brickorna är numrerade 1 till 15 (därav namnet femtonspel). På varje ruta på brädet får bara finnas en bricka, vilket gör att det alltid kommer att finnas en och endast en tom ruta på brädet. Spelet går ut på att från ett godtyckligt startläge flytta en bricka i taget tills normalläget (se fig 1) uppnås. Vid varje brickflyttning flyttas en intilliggande (diagonalt är ej intilliggande) bricka till den tomma rutan (i fig 1 kan bricka 12 eller 15 flyttas och i fig 2 kan bricka 1, 2 eller 7 flyttas). 

Fig 1:  Normalläge      Fig 2:  Ett möjligt startläge
Vid en analys av spelet finner man att man bara från hälften av alla startlägen kan uppnå normalläget. Dessa kallas möjliga startlägen. Om raderna uppifrån numreras 1 till 4 (och kolonnerna 1 till 4 från vänster) måste följande villkor vara uppfyllt för att det skall vara ett möjligt startläge:
(den tomma rutans radnummer + totala antalet inversioner) är ett jämnt tal
En "inversion" föreligger varje gång en bricka med högre nummer är före en bricka med lägre nummer (brickorna tänkes ordnade radvis). Om vi t ex betraktar bricka 13 i fig 2 så ligger den före bricka 1, 4, 5, 10, osv. Åtta av de tio brickorna som ligger efter bricka 13 har lägre nummer, vilket betyder att bricka 13 i fig 2 ger upphov till åtta inversioner.
Fig 2 visar ett möjligt startläge eftersom den tomma rutans radnummer = 1 och antal
inversioner = 
  10 + 6     + 1
 + 5 + 8 + 0 + 1
 + 1 + 3 + 0 + 1
 + 3 + 1 + 1 + 0	= 41.   1 + 41 = 42 (dvs jämnt)

Uppgiften är att avgöra om ett givet brickutseende är ett möjligt startläge eller ej.

Indata:
Rad 1: N, Antal testfall programmet skall behandla.
Därefter följer de N testfallen, som vart och ett består av 4 rader med 4 tal per rad beskrivande brickans utseende, den tomma rutan betecknas med en nolla.

Utdata:
Skall bestå av N rader, en för varje testfall med texten 'Possible' eller 'Impossible', beroende på om det var ett möjligt startläge eller inte.

Exempel:
Indata:
2
11 7 0 2
8 13 1 4
5 10 3 9
15 12 14 6
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 0

Utdata:
Possible
Impossible