Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_20_13 - Laserowy system bezpieczeństwa

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 ≤ 105). 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


Dodane przez:Mariusz Śliwiński
Data dodania:2014-12-24
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.