Infinite Rational Tree

The infinite rational tree is a complete binary tree defined as follows.

• The root is $1/1$.
• The left child of $p/q$ is $p/(p+q)$.
• The right child of $p/q$ is $(p+q)/q$.

The first three levels hold $1/1$ at the top, then $1/2$ and $2/1$, then $1/3$, $3/2$, $2/3$, $3/1$.

Traversing the tree in level order, one level at a time from the top and left to right inside a level, lists its numbers as a sequence of rationals $F(n)$. It begins with $F(1) = 1/1$, $F(2) = 1/2$, $F(3) = 2/1$, $F(4) = 1/3$, $F(5) = 3/2$, $F(6) = 2/3$.

Given a fraction $p/q$ in lowest terms, find the number that comes right after it in this sequence. That is, print $F(n+1)$ when $F(n) = p/q$.

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

Each of the next $P$ lines has a test case number and one fraction in lowest terms, separated by a space.

The fraction is always written as p/q with no space inside it. $p$ is the numerator and $q$ is the denominator.

$p$ and $q$ are coprime and satisfy $1 \le p, q \le 2147483647$. Every given fraction appears in the tree.

For each test case, print the test case number and the answer on one line, separated by a space.

Write the answer in the same numerator/denominator form as the input, with no space between the two numbers.

In every test case the numerator and the denominator of the answer stay inside the 32-bit integer range.