Do bajtockich banków często przybywają kupcy, chcący wypłacić pieniądze ze swoich kont. W każdym banku dostępne są tylko dwa nominały, ale każdego z nich jest nieograniczona liczba. Nie każdą kwotę da się wypłacić, więc banki wywieszają listy, informujące klientów o niedostępnych sumach. Czasami listy te są tak długie, że banki wywieszają tylko początkową część niewypłacalnych kwot.</p>

Kupiec Kozik chce wypłacić dużą kwotę pieniędzy. Zanim wyruszy do banku, to chciałby znać najwyższe kwoty, których banki nie są w stanie wypłacać. Kozik nie ma dostępu do list wywieszonych przez banki. Ma jedynie informację o dostępnych nominałach.

입력 형식

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 10⁶), oznaczającą liczbę bajtockich banków. W następnych n wierszach znajdują się opisy banków. Każdy wiersz zawiera dwie liczby całkowite x, y (1 ≤ x, y ≤ 10⁹), oznaczające wartości dostępnych nominałów.

출력 형식

Standardowe wyjście powinno zawierać n wierszy, będące odpowiedziami dla kolejnych banków. W każdym wierszu powinna znaleźć się jedna liczba całkowita, równa najwyższej kwocie, której bank nie może wypłacić, lub wartość -1, jeśli takiej kwoty nie można ustalić.

예제 입력

3
2 5
3 8
5 10

예제 출력

3
13
-1