POLSKI SPOJ

Szachy uchodzą za skomplikowaną grę. Wszystko przez to, że ilość wszystkich możliwych ustawień figur na szachownicy jest większa niż 10⁴³. Liczba ta nie jest dokładnie poznana, gdyż nawet obecne superkomputery nie są w stanie jej wyznaczyć. Dzisiaj masz okazję przyczynić się do zrozumienia Królewskiej Gry przez komputery. Co więcej, Twoja dzisiejsza praca, dzięki swojej ogólności wniesie swój przyczynek do teorii gier. Bo kto powiedział, że w szachy można grać tylko na szachownicy o wymiarach 8x8?

Na ile sposobów można ustawić na szachownicy 2 króle: białego i czarnego tak aby ich ustawienie było zgodne z przepisami gry w szachy (króle nie mogą stanąć na sąsiadujących polach).

Wejście:

W pierwszej linii wejścia znajduje się jedna liczba n oznaczająca liczbę testów.

W każdym z kolejnych n wierszy znajdują się dwie liczby naturalne: a i b, które oznaczają wymiary szachownicy. 1<=a,b<=1000;

Wyjście:

Dla każdej pary liczb a, b należy podać na ile sposobów można ustawić dwa króle, czarnego i białego tak aby ich ustawienie było legalne.

Przykłady

Wejście:

5

1 1

2 3

8 8

4 1

1 3

Wyjście:

0

8

3612

6

2