Henry

해당 문제는 여기에서 확인하실 수 있습니다.

import math

t = int(input())

for _ in range(t):
    a, b = map(int, input().split())

    while a != 0:
        # 단위분수 분모 계산 (올림)
        x = (b + a - 1) // a

        # 분수 갱신: a/b - 1/x
        a = a * x - b
        b = b * x

        # 기약분수로 약분
        g = math.gcd(a, b)
        a //= g
        b //= g

    # 마지막 단위분수 분모 출력
    print(x)