엘프 혼혈 (Large)

비다는 자신이 엘프 혼혈이라고 말한다. 조상 가운데 적어도 한 명이 엘프였다는 뜻이다. 하지만 그 조상이 부모(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$ 엘프라고 말한다. 비다의 가계에 1/1 엘프가 있었을 수 있는 가장 가까운 세대가 몇 세대 전인지 알려 주어야 한다. 비다가 $P/Q$ 엘프인 것이 불가능하다면, 비다가 틀렸다고 알려 주어야 한다.

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

제한

• $1 \le T \le 100$
• $1 \le P < Q \le 10^{12}$
• $P$와 $Q$는 서로소가 아닐 수 있다. $P/Q$가 기약분수라는 보장은 없다.

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

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

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

$P/Q$가 1/4이면 부모 한쪽이 0/1 엘프, 다른 쪽이 1/2 엘프일 수 있다. 그 1/2 엘프 부모는 다시 1/1 엘프와 0/1 엘프 사이에서 태어날 수 있다. 그래서 2세대 전에 1/1 엘프가 있을 수 있고, 답은 2다.

$P/Q$가 2/23이면, 40세대 전 조상이 모두 0/1 엘프이거나 1/1 엘프인 상태에서 정확히 2/23 엘프가 나올 수 없다. 그래서 답은 impossible이다.

비다의 조상 수가 많다는 점이 이 문제에서 가장 비현실적으로 느껴진다면, 엘프 설명을 다시 읽어 보면 된다.