헨리

열 살이 된 헨리는 수학에 소질이 있다. 수학 선생님 아메스가 오늘 헨리에게 분수를 가르쳐 주었고, 헨리는 분수를 이리저리 계산해 보는 것이 무척 재미있었다. 그러다가 헨리는 1보다 작은 분수를 서로 다른 여러 단위분수의 합으로 나타낼 수 있다는 사실을 알아냈다. 단위분수는 분자가 1인 분수를 말한다. 헨리가 시도해 본 분수는 모두 서로 다른 단위분수의 합으로 표현되었다. 예를 들어 $\frac{4}{23}$은 $\frac{1}{6} + \frac{1}{138}$처럼 단위분수 두 개의 합으로 쓸 수 있다.

헨리는 이 발견을 아메스에게 자랑스럽게 이야기했다. 아메스는 크게 기뻐하며 어린 제자를 칭찬했고, 분수 하나를 서로 다른 단위분수의 합으로 나타낸 것에 헨리식 표현법이라는 이름을 붙였다. 즉 분수 $\frac{a}{b}$의 헨리식 표현법은 합이 $\frac{a}{b}$와 같아지는 서로 다른 단위분수의 나열이다. 두 사람은 연구를 이어 가서 1보다 작은 모든 분수에 헨리식 표현법이 존재함을 증명했다. 헨리식 표현법이 유일하지 않다는 것도 알아냈다. 예를 들어 $\frac{5}{7} = \frac{1}{2} + \frac{1}{5} + \frac{1}{70} = \frac{1}{2} + \frac{1}{6} + \frac{1}{21} = \frac{1}{2} + \frac{1}{7} + \frac{1}{14}$처럼 서로 다른 표현법이 여럿 있을 수 있다. 정의에 따라 같은 단위분수를 두 번 이상 쓸 수 없으므로 $\frac{2}{3} = \frac{1}{3} + \frac{1}{3}$은 헨리식 표현법이 아니다.

아메스와 헨리는 주어진 분수의 헨리식 표현법을 구하는 간단한 방법도 고안했다. $a < b$인 양의 정수 $a$와 $b$로 이루어진 분수 $\frac{a}{b}$가 주어지면, 먼저 $\frac{1}{x_1} \le \frac{a}{b}$를 만족하는 가장 큰 단위분수 $\frac{1}{x_1}$을 구한다. 그다음 $\frac{a}{b}$에서 $\frac{1}{x_1}$을 뺀 나머지에 같은 과정을 반복한다. 즉 $\frac{1}{x_2} \le \frac{a}{b} - \frac{1}{x_1}$을 만족하는 가장 큰 단위분수 $\frac{1}{x_2}$를 구해서 뺀다. 나머지가 0이 될 때까지 이 과정을 반복하면 서로 다른 단위분수 $\frac{1}{x_1}, \frac{1}{x_2}, \frac{1}{x_3}, \dots$을 차례로 얻고, 그 합은 정확히 $\frac{a}{b}$와 같다. 두 사람은 이 알고리즘이 항상 끝나며 합이 $\frac{a}{b}$인 서로 다른 단위분수, 곧 헨리식 표현법을 출력한다는 것을 증명했다.

아메스와 헨리는 이 알고리즘을 프로그램으로 구현해 달라고 부탁했다. 1보다 작은 분수 $\frac{a}{b}$가 주어질 때 아메스와 헨리의 알고리즘으로 헨리식 표현법을 구하고, 마지막 단위분수의 분모를 출력하는 프로그램을 작성하시오. 예를 들어 $\frac{a}{b} = \frac{5}{7}$이면 알고리즘이 $\frac{5}{7} = \frac{1}{2} + \frac{1}{5} + \frac{1}{70}$을 내놓으므로 프로그램은 70을 출력해야 한다.

입력은 표준입력으로 주어진다. 첫 줄에 테스트 데이터의 개수 $T$가 정수로 주어진다. 이어지는 각 테스트 데이터는 한 줄로 이루어지고, 입력 분수 $\frac{a}{b}$를 뜻하는 두 정수 $a$와 $b$ ($1 \le a < b \le 10000$)가 주어진다. $a$와 $b$는 서로소이다. 입력 분수 $\frac{a}{b}$에 아메스와 헨리의 알고리즘을 실행했을 때 나오는 단위분수가 차례로 $\frac{1}{x_1}, \frac{1}{x_2}, \frac{1}{x_3}, \dots, \frac{1}{x_m}$이라면 $b x_1 x_2 \cdots x_{m-1} < 2^{31}$이라고 가정해도 된다.

출력은 표준출력을 사용한다. 각 테스트 데이터마다 정확히 한 줄에 정수 하나를 출력한다. 이 정수는 입력 분수 $\frac{a}{b}$에 아메스와 헨리의 알고리즘을 실행했을 때 나오는 헨리식 표현법의 마지막 단위분수의 분모와 같아야 한다.