유리수 수열

무한히 많은 노드로 이루어진 이진 트리의 각 노드에 다음 규칙으로 유리수를 붙인다.

• 루트의 값은 $1/1$이다.
• 어떤 노드의 값이 $p/q$이면 왼쪽 자식의 값은 $p/(p+q)$, 오른쪽 자식의 값은 $(p+q)/q$이다.

이 트리를 너비 우선으로 방문하되 같은 깊이에서는 왼쪽부터 오른쪽으로 방문해서 유리수 수열 $a_1, a_2, a_3, \dots$를 만든다. 그러면 $a_1 = 1/1$, $a_2 = 1/2$, $a_3 = 2/1$, $a_4 = 1/3$, $a_5 = 3/2$가 된다.

$p$와 $q$가 주어지면 $a_n = p/q$인 정수 $n$을 구하는 프로그램을 작성하시오.

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

다음 $t$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄은 $p$, 문자 /, $q$를 공백 없이 이어 붙인 형태이다. 주어지는 $p/q$는 항상 트리에 나타나는 값이고, 모든 테스트 케이스에서 답 $n$은 32비트 정수 범위에 들어간다.

각 테스트 케이스마다 $a_n = p/q$를 만족하는 정수 $n$을 한 줄에 하나씩 출력한다.