A Rational Sequence 3

An infinite complete binary tree is labeled with positive rational numbers by the following rules.

• The label of the root is $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 the figure below.

Reading the tree in level order, that is breadth first and left to right within each level, gives the rational sequence $F$.

$F(1) = 1/1$, $F(2) = 1/2$, $F(3) = 2/1$, $F(4) = 1/3$, $F(5) = 3/2$, $F(6) = 2/3, \dots$

Given an index $N$, write a program that computes $F(N)$.

The first line contains the number of data sets $P$ ($1 \le P \le 1000$).

Each of the next $P$ lines holds one data set. A line contains the data set number $K$ and the index $N$ of the element to compute ($1 \le N \le 2147483647$). The data sets are numbered $1$ through $P$ in the order they are given.

The data sets are independent and every one is processed the same way.

Print one line for each data set. On that line print the data set number $K$, a single space, the numerator of $F(N)$, the slash character /, and the denominator of $F(N)$, in that order with nothing between them. Do not put a space on either side of the slash.

The input is chosen so that neither the numerator nor the denominator exceeds a 32-bit unsigned integer.