부분 엘프

Vida는 자신이 부분 엘프라고 말한다. 즉, 조상 중 적어도 한 명이 엘프였다는 뜻이다. 하지만 그 조상이 부모였는지(1세대 전), 조부모였는지(2세대 전), 아니면 훨씬 더 여러 세대 전의 누군가였는지는 모른다. 그녀를 도와주자!

부분 엘프가 되는 방식은 아마 여러분이 예상하는 그대로이다. 엘프, 인간, 부분 엘프는 모두 같은 방식으로 태어난다. 두 부모가 만나 아기를 낳는다. 한 부모가 A/B 엘프이고 다른 부모가 C/D 엘프라면, 그들의 아기는 (A/B + C/D) / 2 엘프가 된다. 예를 들어, 0/1 엘프인 사람과 1/2 엘프인 사람이 아기를 낳으면, 그 아기는 1/4 엘프가 된다.

Vida가 한 가지 확신하는 사실이 있다. 40세대 전에 그녀에게는 서로 다른 조상이 2^{40}명 있었으며, 그들 각각은 1/1 엘프이거나 0/1 엘프였다.

Vida는 자신이 P/Q Elf라고 말한다. 그녀의 가계에 1/1 엘프가 존재했을 수 있는 최소 몇 세대 전인지 구하라. 그녀가 P/Q Elf일 가능성이 없다면, 그녀가 틀렸다고 알려 주어라!

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터셋

시간 제한: 60초. 1 ≤ P < Q ≤ 1000. P와 Q에는 공약수가 없다. 즉, P/Q는 기약분수이다.

큰 데이터셋

시간 제한: 120초. 1 ≤ P < Q ≤ $10^{12}$. P와 Q에는 공약수가 있을 수 있다. P/Q가 기약분수라는 보장은 없다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 P/Q 형식의 분수가 하나 주어지며, P와 Q는 정수이다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 그녀가 P/Q Elf일 때 그녀의 가계에 1/1 엘프가 존재했을 수 있는 최소 몇 세대 전인지를 나타낸다. Vida가 P/Q Elf일 수 없다면, y는 문자열 "impossible"이어야 한다(따옴표는 제외한다).

그렇다. Vida에게는 조상이 아주 많다. 문제에서 가장 비현실적으로 보이는 부분이 이것이라면, 엘프에 관한 부분을 다시 읽어 보기 바란다.

다섯 번째 예제 케이스는 작은 입력의 제한을 만족하지 않는다는 점에 유의하라. 이 케이스를 올바르게 풀지 못하더라도 작은 입력은 올바르게 풀었을 수 있다.

예제 케이스 설명

첫 번째 예제 케이스에서 Vida에게는 1/1 엘프인 부모와 0/1 엘프인 부모가 있을 수 있다. 이는 한 세대 전에 1/1 엘프가 존재했을 수 있다는 뜻이므로, 답은 1이다.

두 번째 예제 케이스에서 Vida에게는 1/1 엘프인 부모와 1/2 엘프인 부모가 있었을 수 있다. 이는 한 세대 전에 1/1 엘프가 존재했을 수 있다는 뜻이므로, 답은 1이다.

세 번째 예제 케이스에서 Vida에게는 0/1 엘프인 부모와 1/2 엘프인 부모가 있었을 수 있다. 1/2 엘프인 부모에게는 1/1 엘프인 부모와 0/1 엘프인 부모가 있었을 수 있다. 이는 두 세대 전에 1/1 엘프가 존재했을 수 있다는 뜻이므로, 답은 2이다.

네 번째 예제 케이스에서 40세대 전의 조상이 모두 0/1 엘프이거나 1/1 엘프였다면 정확히 2/23 엘프가 되는 것은 불가능하다.