Rational Sequence

Label the nodes of an infinite rooted binary tree with rational numbers by the following rule.

• The root is labeled $1/1$.
• If a node is labeled $p/q$, then its left child is labeled $p/(p+q)$ and its right child is labeled $(p+q)/q$.

Traverse this tree in breadth first order, visiting the nodes of the same depth from left to right, and read off the rational sequence $a_1, a_2, a_3, \dots$. This gives $a_1 = 1/1$, $a_2 = 1/2$, $a_3 = 2/1$, $a_4 = 1/3$, $a_5 = 3/2$.

Given $p$ and $q$, write a program that computes the integer $n$ with $a_n = p/q$.

The first line contains the number of test cases $t$ ($1 \le t \le 1000$).

Each of the next $t$ lines holds one test case: $p$, the character /, and $q$, written with no spaces between them. Every given $p/q$ appears in the tree, and in every test case the answer $n$ fits in a 32-bit integer.

For each test case, print on its own line the integer $n$ with $a_n = p/q$.