무한 유리수 트리

무한 유리수 트리는 완전 이진 트리이며 다음과 같이 정의된다.

• 루트는 $1/1$이다.
• $p/q$의 왼쪽 자식은 $p/(p+q)$이다.
• $p/q$의 오른쪽 자식은 $(p+q)/q$이다.

첫 세 층은 맨 위가 $1/1$, 그 아래가 $1/2$와 $2/1$, 그 아래가 $1/3$, $3/2$, $2/3$, $3/1$이다.

이 트리를 레벨 오더로, 즉 위층부터 한 층씩 훑으면서 같은 층에서는 왼쪽에서 오른쪽으로 훑어 나열하면 유리수 수열 $F(n)$을 얻는다. 앞의 몇 항은 $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$일 때 $F(n+1)$을 출력한다.

첫 줄에 테스트 케이스의 수 $P$가 주어진다. ($1 \le P \le 1000$)

다음 $P$개의 줄에는 각각 테스트 케이스의 번호와 기약분수 하나가 공백으로 구분되어 주어진다.

기약분수는 항상 p/q 꼴이고 그 안에 공백은 없다. $p$는 분자, $q$는 분모이다.

$p$와 $q$는 서로소이며 $1 \le p, q \le 2147483647$을 만족한다. 주어지는 분수는 항상 트리에 나타나는 값이다.

각 테스트 케이스마다 테스트 케이스의 번호와 답을 공백으로 구분해 한 줄에 출력한다.

답이 되는 기약분수는 입력과 같은 분자/분모 꼴로 쓰고, 사이에 공백을 두어서는 안 된다.

모든 테스트 케이스에서 답의 분자와 분모는 32비트 정수 범위를 넘지 않는다.