엘프 혈통 (Small)

비다는 자신에게 엘프의 피가 섞여 있다고 말한다. 조상 가운데 적어도 한 명이 엘프였다는 뜻이다. 그런데 그 조상이 부모(1세대 전)인지, 조부모(2세대 전)인지, 아니면 훨씬 먼 세대인지는 비다도 모른다. 비다를 도와주자.

엘프의 피는 짐작하는 대로 이어진다. 엘프도, 인간도, 피가 섞인 사람도 모두 같은 방식으로 태어난다. 부모 한 명이 A/B 엘프이고 다른 한 명이 C/D 엘프이면 그 아이는 (A/B + C/D) / 2 엘프다. 예를 들어 0/1 엘프와 1/2 엘프 사이에서 태어난 아이는 1/4 엘프다.

비다가 확실하게 아는 사실이 하나 있다. 40세대 전 비다에게는 서로 다른 조상이 $2^{40}$명 있었고, 그 조상은 모두 1/1 엘프이거나 0/1 엘프였다.

비다는 자신이 $P/Q$ 엘프라고 말한다. 비다가 $P/Q$ 엘프일 때 가계에 1/1 엘프가 있었을 수 있는 가장 가까운 세대가 몇 세대 전인지 알려 주자. 비다가 $P/Q$ 엘프인 것이 아예 불가능하다면 그렇다고 알려 주면 된다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 줄에 $P/Q$ 꼴의 분수가 한 줄에 하나씩 주어진다. $P$와 $Q$는 정수다.

제한

• $1 \le T \le 100$
• $1 \le P < Q \le 100000$
• $P/Q$는 기약분수로 주어지지 않을 수도 있다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 비다가 $P/Q$ 엘프일 때 1/1 엘프 조상이 있었을 수 있는 최소 세대 수다. 비다가 $P/Q$ 엘프인 것이 불가능하면 $y$ 자리에 따옴표 없이 impossible을 출력한다.

비다가 1/2 엘프라면 부모 한 명은 1/1 엘프, 다른 한 명은 0/1 엘프일 수 있다. 1세대 전에 1/1 엘프가 있으므로 답은 1이다.

비다가 3/4 엘프라면 부모 한 명은 1/1 엘프, 다른 한 명은 1/2 엘프일 수 있다. 이때도 1세대 전에 1/1 엘프가 있으므로 답은 1이다.

비다가 1/4 엘프라면 부모는 0/1 엘프와 1/2 엘프일 수 있고, 그 1/2 엘프 부모의 부모가 1/1 엘프와 0/1 엘프일 수 있다. 그래서 답은 2다.

40세대 전 조상이 모두 0/1 엘프이거나 1/1 엘프였다면 정확히 2/23 엘프가 되는 일은 없다.

조상 수가 지나치게 많아 보인다면, 엘프에 관한 설명을 다시 읽어 보자.