유리수 트리

루트 정점이 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, ...

다음 두 질문을 해결하라:

• n이 1부터 시작할 때, 배열의 n번째 원소를 구하라. 예를 들어 입력이 2이면 올바른 출력은 1/2이다.

• p/q가 주어질 때, 배열에서 그 위치를 구하라. 예를 들어 입력이 1/2이면 출력은 2이다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

1 ≤ T ≤ 100; p와 q는 서로소이다.

테스트 세트 1 - 공개

1 ≤ n, p, q ≤ $2^{16}$-1; p/q는 레벨 번호가 ≤ 16인 트리의 원소이다.

테스트 세트 2 - 비공개

1 ≤ n, p, q ≤ $2^{64}$-1; p/q는 레벨 번호가 ≤ 64인 트리의 원소이다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 이루어진다. 이 줄에는 문제 식별자(1 또는 2)와 한 개 또는 두 개의 추가 정수가 주어진다:

• 문제 식별자가 1이면 정수 n 하나만 주어지며, 배열의 n번째 원소를 구해야 한다.

• 문제 식별자가 2이면 두 정수 p와 q가 주어지며, 배열에서 p/q의 위치를 구해야 한다.

각 테스트 케이스에 대해:

• 문제 식별자가 1이면 "Case #x: p q"을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, p와 q은 각각 요청한 배열 원소의 분자와 분모이다.

• 문제 식별자가 2이면 "Case #x: n"을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, n은 주어진 수의 위치이다.