33473번 - Bee Tea Again 서브태스크

문제

2021년 여름, 동우와 유신이를 중심으로 비공개 대회인 수학과 보안, 알고리즘이 혼합된 대회인 <제1회 CodeComment Cup>이 개최되었다. 그 이후 대회가 사라졌다가, 동우와 재우를 포함한 당시 사이버국방학과 몇몇 학생의 주도로 MatKor가 만들어졌던 2022년 여름, 대회를 부활시키고자 했다. 동우와 재우는 내부 대회로 <제1회 MatKor Cup : 2022 Summer>를 개최하기로 하였고, <제1회 CodeComment Cup>의 명칭을 <제0회 MatKor Cup>으로 변경하였다.

<제1회 MatKor Cup : 2022 Summer> 당시 발생한 KOVID-22 바이러스에 이어 KOVID-25 바이러스가 발생하였다!

KOVID-25 바이러스에 감염이 된 사람들은 국가에서 특별히 관리하여 격리한다. 감염된 사람들은 각자 한 명당 하나의 방에 격리되는데, 방들은 직선 형태의 복도에 배치되어 있고, 정수 $i$에 대하여 $i$번 방은 $i$ 이상 $i+1$ 미만의 좌표 범위를 의미한다. 감염된 사람들은 1ドル$번 방부터 2ドル$번 방, 3ドル$번 방과 같이 방의 번호가 커지는 순서대로 차례로 격리되며, 0ドル$번 방에는 격리 시설의 관리자 동우가 있다. 또 다른 관리자인 재우는 양이 아닌 정수 $-N(N\ge 0)$번 방에 있다.

KOVID-25 바이러스의 경우 벌집에서 추출한 꿀로 만든 차를 마셔야 금방 낫기 때문에 동우와 재우는 벌꿀차를 만들어 격리자들에게 나누어 주려 한다. 동우와 재우는 각자 보폭에 맞추어 벌꿀차를 나누어 주는데, 동우의 보폭은 $A,ドル 재우의 보폭은 $B$이다. 구체적으로 동우는 0ドル$의 좌표, 재우는 $-N$의 좌표에서 출발해 독립적으로 다음과 같이 벌꿀차를 나누어 준다. 처음에 격리자들은 벌꿀차를 가지고 있지 않다.

1. 먼저 현재 위치에서 오른쪽(양의 방향)으로 각자 보폭만큼 움직인다.
2. 움직인 후 위치한 방에 격리자가 있는지 여부에 따라 다음을 시행한다.
   • 격리자가 있다면 다음을 시행한다. 동우나 재우는 제자리에서 이 행동을 하므로 위치가 변하지 않는다. 이후 1번 행동으로 돌아가 반복한다.
     • 만약 격리자가 벌꿀차를 가지고 있지 않다면, 벌꿀차를 준다.
     • 만약 이미 격리자가 벌꿀차를 가지고 있다면, 벌꿀차를 회수한다.
   • 격리자가 없다면 행동을 종료한다.

동우와 재우의 보폭에 따라 같은 관리자가 같은 방을 여러 번 열 수도 있다는 점에 유의하자.

이때 격리자들의 불만이 생길 수 있으므로, 최종적으로 모든 과정이 끝난 후 모든 격리자가 벌꿀차를 가지고 있도록 하고 싶다. 또한, 격리자가 몇 명이나 될지 모르기 때문에, 아무리 많은 사람이 오더라도 격리자들의 불만이 생기지 않도록 동우와 재우는 보폭을 서로 맞추려 한다. 동우의 보폭이 $A$일 때, 이 조건을 만족하도록 재우의 보폭을 정해보자. 재우는 보폭을 정한 후에, 본인이 있을 방을 정할 것이므로 조건을 만족하는 방이 하나라도 있으면 해당 보폭은 가능한 것으로 생각한다.

또한 동우와 재우의 보폭은 10ドル^{18}$ 이하의 양의 정수이거나 기약분수로 나타냈을 때, 분모와 분자가 모두 10ドル^{18}$ 이하인 양의 유리수를 만족해야 한다.

입력

첫 번째 줄에 테스트 케이스의 개수 $T(1\le T\le 10^6)$가 주어진다.

각 테스트 케이스의 첫 번째 줄에 동우의 보폭을 나타내는 서로소인 두 양의 정수 $P,Q(1\le P,Q\le 10^{18})$가 공백으로 구분되어 주어진다. 이는 $A=\frac{Q}{P}$라는 의미이다.

출력

각 테스트 케이스의 첫 번째 줄에 조건을 만족하는 재우의 보폭으로 가능한 개수를 출력한다.

제한

서브태스크

힌트