Henry

Henry is ten years old and has a talent for mathematics. His mathematics teacher, Ahmes, taught him fractions today, and Henry enjoyed computing with them. While playing around he discovered that a fraction smaller than 1 can be written as a sum of several distinct unit fractions. A unit fraction is a fraction whose numerator is 1. Every fraction Henry tried turned out to be a sum of distinct unit fractions. For example, $\frac{4}{23}$ can be written as a sum of two unit fractions, $\frac{1}{6} + \frac{1}{138}$.

Henry proudly told Ahmes about the discovery. Ahmes was delighted, praised his young student, and named such a sum of distinct unit fractions a Henry representation. The Henry representation of a fraction $\frac{a}{b}$ is a list of distinct unit fractions whose total equals $\frac{a}{b}$. The two of them studied the idea further and proved that every fraction smaller than 1 has a Henry representation. They also found that a Henry representation is not unique. For example, $\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}$ gives three different Henry representations. By the definition, the same unit fraction cannot appear twice, so $\frac{2}{3} = \frac{1}{3} + \frac{1}{3}$ is not a Henry representation.

Ahmes and Henry also devised a simple method for finding a Henry representation. Given a fraction $\frac{a}{b}$ built from positive integers $a$ and $b$ with $a < b$, first compute the largest unit fraction $\frac{1}{x_1}$ with $\frac{1}{x_1} \le \frac{a}{b}$. Then repeat the same process on what is left after subtracting $\frac{1}{x_1}$ from $\frac{a}{b}$: compute the largest unit fraction $\frac{1}{x_2}$ with $\frac{1}{x_2} \le \frac{a}{b} - \frac{1}{x_1}$ and subtract it. Repeat until nothing is left. This yields distinct unit fractions $\frac{1}{x_1}, \frac{1}{x_2}, \frac{1}{x_3}, \dots$ in order, and their sum is exactly $\frac{a}{b}$. Ahmes and Henry proved that the algorithm always terminates and outputs distinct unit fractions summing to $\frac{a}{b}$, that is, a Henry representation.

Ahmes and Henry asked you to implement their algorithm as a computer program. Given a fraction $\frac{a}{b}$ smaller than 1, run the algorithm of Ahmes and Henry and print the denominator of the last unit fraction of the Henry representation it produces. For example, if $\frac{a}{b} = \frac{5}{7}$, the algorithm produces $\frac{5}{7} = \frac{1}{2} + \frac{1}{5} + \frac{1}{70}$, so your program must print 70.

Read the input from standard input. The first line contains the number of test data $T$ as an integer. Each test datum is one line holding two integers $a$ and $b$ ($1 \le a < b \le 10000$), which denote the input fraction $\frac{a}{b}$. The integers $a$ and $b$ are coprime. If running the algorithm of Ahmes and Henry on $\frac{a}{b}$ produces the unit fractions $\frac{1}{x_1}, \frac{1}{x_2}, \frac{1}{x_3}, \dots, \frac{1}{x_m}$ in this order, you may assume that $b x_1 x_2 \cdots x_{m-1} < 2^{31}$.

Write the output to standard output. For each test datum print exactly one line containing a single integer. That integer must equal the denominator of the last unit fraction of the Henry representation produced by the algorithm of Ahmes and Henry on the input fraction $\frac{a}{b}$.