AlgoLiga 2018

Laserowy system bezpieczeństwa

W banku, którym pracuje Jasiu, wprowadzono w niektórych pomieszczeniach laserowy system bezpieczeństwa. W pomieszczeniu takim w kształcie prostokąta o wymiarach m × n równomiernie rozmieszczonych jest (m+1) × (n+1) punktów kratowych, pomiędzy którymi można włączyć wiązkę laserową. Ustalono, że w każdym takim pomieszczeniu nie może być dwóch wiązek, które będą równoległe. Jasia, który ma nadzorować system, interesuje, ile najwięcej takich wiązek laserowych może być jednocześnie aktywowanych w pomieszczeniu. Ponieważ nie sposób policzyć to zawsze w pamięci, trzeba napisać program. To zadanie dla Ciebie.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (d ≤ 10⁵). Każdy przypadek opisany jest w osobnym wierszu, gdzie podane są dwie liczby całkowite m, n (1 ≤ m, n ≤ 1000) oznaczające wymiary pomieszczenia, w którym jest dokładnie (m+1) × (n+1) punktów kratowych, między parami których można włączyć wiązkę laserową.

Wyjście
Dla każdego przypadku testowego należy wypisać jedną liczbę - największą liczbę wiązek laserowych, które jednocześnie mogą strzec kosztowności w pomieszczeniu. Innymi słowy, jaka jest największa liczba linii prostych, które można poprowadzić przez dwa punkty kratowe siatki tak, aby żadne dwie nie były równoległe?

Przykład

Wejście
2
2 1
3 5

Wyjście
6
26