저 집합은 해로운 집합이다

집합론을 공부하던 승현이는 다음 집합을 알게 됐다.

$C_0 = [0, 1]$

$C_n = \left\{\, a + \sum_{i=1}^{n} \frac{a_i}{3^i} \;\middle|\; 0 \le a \le \frac{1}{3^n},\; a_i \in \{0, 2\} \,\right\} \quad (n \in \mathbb{N})$

$C = \bigcap_{n=0}^{\infty} C_n$

$C$가 잘 이해되지 않던 승현이는 두 가지 작업을 계획했다. 첫 번째는 유리수를 하나 골라 그 수가 $C$에 들어가는지 확인하는 작업이다. 들어가지 않으면 두 번째 작업으로 넘어가서, 그 수를 포함하지 않는 집합 중 아랫첨자 $n$이 가장 작은 집합을 찾는다.

몇 번 손으로 해 보니 이 작업이 몹시 귀찮아진 승현이는 컴퓨터를 쓰기로 했다. 그런데 코딩까지 귀찮았는지 후배인 당신에게 일을 넘겼다. 얼떨결에 거절하지 못하고 일을 떠맡은 당신은 승현이를 골탕 먹일 심보로 불완전한 판정 프로그램을 만들기로 했다.

답이 너무 이상하게 나오면 승현이가 속지 않을 테니 적당히 그럴듯하게 출력해야 한다. 그래서 $C_0$부터 $C_{10}$까지에 대해서만 포함 여부를 확인하고, 이 열한 개 집합이 모두 그 수를 포함하면 $C$에 포함된다고 판정하기로 했다. 이 조건을 만족하는 불완전한 프로그램을 작성하자.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

다음 $T$개 줄에는 유리수의 분자 $a$와 분모 $b$가 공백을 사이에 두고 주어진다. ($0 \le a \le 100000$, $1 \le b \le 100000$)

각 테스트 케이스마다 한 줄씩 출력한다.

$C_0$부터 $C_{10}$까지 중 $\frac{a}{b}$를 포함하지 않는 집합이 있으면 그중 아랫첨자 $n$이 가장 작은 집합의 $n$을 출력한다. 열한 개 집합이 모두 포함하면 -1을 출력한다.

$C_1 = \left[0, \frac{1}{3}\right] \cup \left[\frac{2}{3}, 1\right]$이고, $C_2 = \left[0, \frac{1}{9}\right] \cup \left[\frac{2}{9}, \frac{1}{3}\right] \cup \left[\frac{2}{3}, \frac{7}{9}\right] \cup \left[\frac{8}{9}, 1\right]$이다.

$\frac{1}{2}$은 $C_0$에는 들어가지만 $C_1$에는 들어가지 않는다. $\frac{1}{6}$은 $C_1$까지는 들어가고 $C_2$에서 처음으로 빠진다.

분자가 0인 수는 집합 정의에서 $a = 0$, 모든 $a_i = 0$으로 두면 되므로 $C_0$부터 $C_{10}$까지 전부 포함한다.

$\frac{a}{b}$가 1보다 크면 $C_0$부터 이미 포함하지 않으므로 0을 출력한다.