#216513. [GKS 2013 #A] Rational Number Tree

Consider an infinite complete binary tree where the root node is and left and right childs of node are and , respectively. This tree looks like:

:::align{center} :::

It is known that every positive rational number appears exactly once in this tree. A level-order traversal of the tree results in the following array:

, , , , , , ,

Please solve the following two questions:

1. Find the -th element of the array, where starts from . For example, for the input , the correct output is .
2. Given , find its position in the array. As an example, the input results in the output .

The first line of the input gives the number of test cases, . test cases follow. Each test case consists of one line. The line contains a problem id ( or ) and one or two additional integers:

1. If the problem id is , then only one integer is given, and you are expected to find the -th element of the array.
2. If the problem id is , then two integers and are given, and you are expected to find the position of in the array.

For each test case:

1. If the problem id is , then output one line containing "Case #x: p q", where is the case number (starting from ), and are numerator and denominator of the asked array element, respectively.
2. If the problem id is , then output one line containing "Case #x: n", where is the case number (starting from ), and is the position of the given number.

样例输入 1

4
1 2
2 1 2
1 5
2 3 2

样例输出 1

Case #1: 1 2
Case #2: 2
Case #3: 3 2
Case #4: 5

Limits

; and are relatively prime.

Test set 1 - Visible

; is an element in a tree with level number .

Test set 2 - Hidden

; is an element in a tree with level number .