유리수 수열 3

양의 유리수를 라벨로 갖는 무한 완전 이진 트리를 다음과 같이 정의한다.

• 루트의 라벨은 $1/1$이다.
• 라벨이 $p/q$인 노드의 왼쪽 자식의 라벨은 $p/(p+q)$이다.
• 라벨이 $p/q$인 노드의 오른쪽 자식의 라벨은 $(p+q)/q$이다.

트리의 위쪽 부분은 아래 그림과 같다.

이 트리를 레벨 순서로, 즉 너비 우선으로 각 레벨의 왼쪽 노드부터 읽으면 유리수 수열 $F$를 얻는다.

$F(1) = 1/1$, $F(2) = 1/2$, $F(3) = 2/1$, $F(4) = 1/3$, $F(5) = 3/2$, $F(6) = 2/3, \dots$

인덱스 $N$이 주어지면 $F(N)$을 구하는 프로그램을 작성하시오.

첫째 줄에 데이터 집합의 개수 $P$가 주어진다. ($1 \le P \le 1000$)

다음 $P$개 줄에 데이터 집합이 한 줄에 하나씩 주어진다. 각 줄은 데이터 집합 번호 $K$와 구할 원소의 인덱스 $N$으로 이루어진다. ($1 \le N \le 2147483647$) 데이터 집합은 주어진 순서대로 $1$번부터 $P$번까지 번호가 매겨져 있다.

각 데이터 집합은 서로 독립이고, 모두 같은 방식으로 처리한다.

각 데이터 집합마다 한 줄씩 출력한다. 데이터 집합 번호 $K$, 공백 한 칸, $F(N)$의 분자, 슬래시 문자 /, $F(N)$의 분모를 이 순서로 이어서 출력한다. 슬래시 앞뒤에는 공백을 넣지 않는다.

분자와 분모가 모두 32비트 부호 없는 정수 범위를 넘지 않도록 입력이 주어진다.