유리수 트리

루트가 $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^{64} - 1$
• $p$와 $q$는 서로소이다.
• $p/q$는 레벨 번호가 64 이하인 노드에 있다. 루트의 레벨 번호는 1이다.