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