유리수 트리 (작은 입력)

무한한 포화 이진 트리를 생각한다. 루트는 $1/1$이고, 노드 $p/q$의 왼쪽 자식은 $p/(p+q)$, 오른쪽 자식은 $(p+q)/q$이다. 트리의 위쪽은 다음과 같은 모양이다.

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

모든 양의 유리수가 이 트리에 정확히 한 번씩 나타난다는 사실이 알려져 있다. 트리를 레벨 순서로 훑으면 다음 배열을 얻는다.

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

다음 두 가지 질의를 처리한다.

1. 배열의 $n$번째 원소를 구한다. $n$은 1부터 센다. 예를 들어 $n$이 2이면 답은 $1/2$이다.
2. 기약분수 $p/q$가 배열에서 몇 번째인지 구한다. 예를 들어 $1/2$이 주어지면 답은 2이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄은 질의 번호(1 또는 2)와 정수 한 개 또는 두 개로 이루어진다.

1. 질의 번호가 1이면 정수 $n$ 하나가 주어진다. 배열의 $n$번째 원소를 구해야 한다.
2. 질의 번호가 2이면 정수 $p$와 $q$가 주어진다. $p/q$가 배열에서 몇 번째인지 구해야 한다.

각 테스트 케이스마다 한 줄을 출력한다.

1. 질의 번호가 1이면 Case #x: p q를 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, p와 q는 구한 원소의 분자와 분모이다.
2. 질의 번호가 2이면 Case #x: n을 출력한다. x는 테스트 케이스 번호이고, n은 주어진 수의 위치이다.

• $1 \le T \le 100$
• $1 \le n, p, q \le 2^{16} - 1$
• $p$와 $q$는 서로소이다.
• $p/q$는 레벨 번호가 16 이하인 노드에 있다. 루트의 레벨 번호는 1이다.