은행

바이트랜드의 은행에는 계좌에서 돈을 인출하려는 상인들이 자주 찾아온다. 각 은행에서는 딱 두 종류의 화폐 단위만 쓸 수 있지만, 각 단위의 지폐는 무제한으로 있다. 모든 금액을 인출할 수 있는 것은 아니어서, 은행은 인출이 불가능한 금액을 알리는 목록을 게시한다. 이 목록이 너무 길어질 때는 은행이 앞부분의 인출 불가능 금액만 게시하기도 한다.

상인 코지크는 큰 금액을 인출하려 한다. 은행에 가기 전에, 그는 각 은행이 인출해 줄 수 없는 가장 큰 금액을 알고 싶어 한다. 코지크는 은행이 게시한 목록을 볼 수 없고, 사용 가능한 화폐 단위 값만 알고 있다.

첫 번째 줄에 은행의 수를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어진다. 이어지는 $n$개의 줄에는 각 은행의 정보가 한 줄씩 주어진다. 각 줄에는 그 은행에서 사용할 수 있는 두 화폐 단위의 값을 나타내는 정수 $x$, $y$ ($1 \le x, y \le 10^9$)가 주어진다.

$n$개의 줄을 출력한다. 각 줄에는 입력 순서대로 해당 은행이 인출해 줄 수 없는 가장 큰 금액을 정수로 출력한다. 그런 금액을 정할 수 없으면 $-1$을 출력한다.