A Rational Sequence

A sequence of positive rational numbers comes from an infinite complete binary tree whose nodes are labeled by positive rationals.

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

The top of the tree looks like this:

The sequence $F$ comes from a level order (breadth first) traversal of the tree, drawn as the light dashed line in the figure. That gives $F(1) = 1/1$, $F(2) = 1/2$, $F(3) = 2/1$, $F(4) = 1/3$, $F(5) = 3/2$, $F(6) = 2/3$, and so on.

Given $p$ and $q$, find the value of $n$ for which $F(n) = p/q$.

The first line contains one integer $P$, the number of data sets ($1 \le P \le 1000$). Each data set is independent of the others and is processed the same way.

Each of the next $P$ lines holds one data set: the data set number $K$, a single space, the numerator $p$, a forward slash (/), and the denominator $q$. Every fraction given is in lowest terms, so it appears exactly once in the tree.

Print one line per data set: the data set number $K$, a single space, and the value of $n$ for which $F(n) = p/q$. The inputs are chosen so that $n$ fits in a signed 32-bit integer.