유리수 수열

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

• 루트의 이름표는 $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$과 같이 이어진다.

$p$와 $q$가 주어질 때 $F(n) = p/q$인 $n$을 구하는 프로그램을 작성하시오.

첫째 줄에 데이터 집합의 개수 $P$가 주어진다. ($1 \le P \le 1000$) 각 데이터 집합은 서로 독립이며 모두 같은 방식으로 처리한다.

다음 $P$개의 줄에 데이터 집합이 한 줄씩 주어진다. 각 줄은 데이터 집합 번호 $K$, 공백 하나, 분자 $p$, 슬래시(/), 분모 $q$로 이루어진다. 주어지는 분수는 모두 기약분수이므로 트리에 정확히 한 번 나타난다.

데이터 집합마다 한 줄씩 출력한다. 데이터 집합 번호 $K$, 공백 하나, $F(n) = p/q$를 만족하는 $n$을 차례로 출력한다. $n$이 부호 있는 32비트 정수에 들어가도록 입력이 주어진다.