Rational Number Tree (Small)

Consider an infinite complete binary tree whose root is $1/1$, where the left child of the node $p/q$ is $p/(p+q)$ and the right child is $(p+q)/q$. The top of the tree looks like this.

         1/1
    ______|______
    |           |
   1/2         2/1
 ___|___     ___|___
 |     |     |     |
1/3   3/2   2/3   3/1
...

Every positive rational number is known to appear in this tree exactly once. Traversing the tree in level order gives the following array.

1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...

Answer the following two kinds of queries.

1. Find the $n$-th element of the array, counting from $n = 1$. For example, if $n$ is 2, the answer is $1/2$.
2. Given a fraction $p/q$ in lowest terms, find its position in the array. For example, given $1/2$, the answer is 2.

The first line contains the number of test cases $T$. The next $T$ lines each hold one test case. Each line contains a query id (1 or 2) and one or two integers.

1. If the query id is 1, one integer $n$ follows, and you must find the $n$-th element of the array.
2. If the query id is 2, two integers $p$ and $q$ follow, and you must find the position of $p/q$ in the array.

Print one line for each test case.

1. If the query id is 1, print Case #x: p q, where x is the test case number starting from 1, and p and q are the numerator and the denominator of the requested element.
2. If the query id is 2, print Case #x: n, where x is the test case number and n is the position of the given number.

• $1 \le T \le 100$
• $1 \le n, p, q \le 2^{16} - 1$
• $p$ and $q$ are coprime.
• $p/q$ sits at a node whose level number is at most 16. The root has level number 1.