Schaken op een Möbiusband
Beschrijving
Uit de algebraïsche topologieën uit diverse knutselboeken is
de zogenaamde Möbiusband bekend. Je krijgt hem door één uiteinde
van een strook papier 180° te draaien en aan het andere
uiteinde te plakken. Het leuke van zo'n band is dat je, als je over
het oppervlak loopt zowel de `binnenkant' als de `buitenkant'
tegenkomt. In deze opgave gaan we schaken met koninginnen op zo'n
Möbiusband.
Het Probleem
Je krijgt de opdracht een programma te schrijven dat voor een Möbiusband
van gegeven afmetingen bepaalt hoeveel koninginnen op die Möbiusband
geplaatst kunnen worden zonder dat ze elkaar slaan. Voor de
niet-schakers: een koningin kan horizontaal, verticaal en diagonaal
lopen en slaan over een willekeurige afstand, slechts begrensd door de
rand van het bord en andere stukken.
De Invoer
De invoer begint met één regel met daarop het aantal runs. Daarna
volgt per run een regel met daarop de lengte n van één kant en
de breedte m van de Möbiusband, waarbij 1 <= n, m <= 10.
De uitvoer bestaat per run uit één regel met daarop het maximale
aantal koninginnen dat valt te plaatsen op de Möbiusband van gegeven
afmetingen.
Voorbeeld
Bij de invoer
2
2 2
3 3
hoort de uitvoer
2
3