집합론을 공부하던 승현이는 다음과 같은 집합을 알게 됐다.</p>

[C_0 = \left[0,1\right] \ C_n = \left{ a+\sum_{i=1}^{n} {\frac{a_i}{3^i}} \mid 0 \le a \le \frac{1}{3^n}, a_i \in \left{0, 2\right} \right} \text{ for } n \in \mathbb{N} \ C = \bigcap_{n=0}^{\infty}{C_n}]

(C)라는 집합이 잘 이해가 되지 않던 승현이는 이해를 하기 위해 몇 가지 작업을 계획했다. 첫 번째 작업은 어떤 유리수 한 개를 임의로 골랐을 때 그 수가 집합 안에 들어가는지 안 들어가는지 확인하는 작업이다. 만약 집합 안에 들어가지 않는다면 두 번째 작업을 이어서 하게 되는데, 이 작업은 그 유리수를 처음으로 포함하지 않는, 즉 가장 작은 (n)을 갖는 집합을 찾는 것이다.

몇 번 손으로 작업하는 승현이는 이 작업이 매우 귀찮아졌다. 그래서 컴퓨터를 사용하기로 했는데 코딩을 하는 것도 귀찮아졌는지 갑자기 이 일을 후배인 당신에게 시켰다. 얼떨결에 거절하지 못하고 이 일을 받게 된 당신은 승현이를 골탕 먹여줄 심보로 불완전한 판정 프로그램을 만들기로 했다.

너무 답이 이상하게 나오면 속지 않을 것을 걱정한 당신은 적당히 그럴듯하게 답을 출력하기로 했다. 이를 위해 (C_0)부터 (C_{10})까지에 대해서만 수의 포함 여부를 확인하고 만약 모든 집합이 수를 포함한다면 포함된다고 판정하는 프로그램을 만들 것이다. 승현이를 골려주기 위해 위 조건을 만족하는 불완전한 프로그램을 작성하자!!

입력 형식

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스마다 유리수를 나타내는 정수 a와 b(0 ≤ a ≤ 100,000, 1 ≤ b ≤ 100,000)가 빈칸을 사이에 두고 주어진다. 이때 a는 분자, b는 분모를 나타낸다.

출력 형식

한 테스트 케이스 당 한 줄에 걸쳐 주어진 유리수가 (C_0)부터 (C_{10})사이에 포함되지 않으면 처음으로 포함되지 않는 집합의 아랫첨자 (n)을 출력하고 포함하면 -1을 출력한다.

예제 입력

4
0 1
1 2
1 6
5 18

예제 출력

-1
1
2
3

힌트

첫 번째 입력의 경우 (a_i = 0, a = 0) 일 때 모든 집합에 대해 포함된다.</p>

두 번째 입력의 경우 (C_0 = \left[0,1\right], C_1 = \left[0,\frac{1}{3}\right] \cup \left[\frac{2}{3},1\right]) 이므로 (\frac{1}{2})는 (C_1)에서 처음으로 포함되지 않는다.

세 번째 입력의 경우 (C_0), (C_1)은 위와 같고, (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]) 이므로 (C_2)에서 처음으로 포함되지 않는다.