시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 76 18 17 37.778%

문제

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

\[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}\)까지에 대해서만 수의 포함 여부를 확인하고 만약 모든 집합이 수를 포함한다면 포함된다고 판정하는 프로그램을 만들 것이다. 승현이를 골려주기 위해 위 조건을 만족하는 불완전한 프로그램을 작성하자!!

입력

입력의 첫 줄에는 테스트 케이스의 수 가 주어진다. 각 테스트 케이스마다 유리수를 나타내는 정수 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\) 일 때 모든 집합에 대해 포함된다.

두 번째 입력의 경우 \(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\)에서 처음으로 포함되지 않는다.