문제
이제 10 살이 된 헨리(Henry)는 수학에 소질이 있다. 수학선생님인 아메스(Ahmes)는 오늘 헨리에게 분수에 대해 가르쳐줬고, 헨리는 분수를 이리저리 계산해보는 것이 너무 재미있었다. 그러던 중에 헨리는 1 보다 작은 분수를 여러 개의 서로 다른 단위분수의 합으로 표현할 수 있다는 것을 알아내었다. 여기서 단위분수란 분자가 1 인 분수를 말한다. 헨리는 여러 개의 분수에 대해 이를 시도해봤고, 시도해본 분수들은 모두 서로 다른 단위분수의 합으로 표현할 수 있었다. 예를 들어, 4/23 은 1/6 + 1/138와 같이 두 개의 단위 분수의 합으로 나타낼 수 있다.
헨리는 이런 발견을 선생님인 아메스에게 자랑스럽게 이야기했다. 아메스는 이를 듣고는 크게 기뻐하며 어린 제자를 칭찬했고, 이와 같이 하나의 분수를 서로 다른 단위분수의 합으로 표현한 것을 헨리식 표현법(Henry representation)이라고 이름 지었다. 즉, 분수 a/b의 헨리식 표현법은 총합이 a/b 와 같게 되는 서로 다른 단위분수의 나열이다. 헨리와 아메스는 헨리식 표현법에 대하여 더욱 연구하였고, 마침내 모든 1 보다 작은 분수는 헨리식 표현법이 가능함을 증명하였다. 또한 헨리식 표현법이 유일하지 않다는 것도 알 수 있었다.
# 10253
import sys
input = lambda: sys.stdin.readline().strip()
# 1. 1 / x1 <= a / b => x1 >= b / a 을 만족하는 최소
# 2. 1 / xn <= (a /b - 1 / x(n-1)) = a' / b' => xn >= b' / a' 을 만족하는 최소
# 3. 마지막 단위 분수의 분모 출력
import math
t = int(input())
for _ in range(t):
a, b = map(int, input().split())
while a > 1:
x = math.ceil(b / a)
if a * x - b > 0:
a, b = a * x - b, b * x
else:
break
b = b // math.gcd(a, b)
print(b)