Part Elf (Large)

Vida says she is part Elf: at least one of her ancestors was an Elf. She does not know whether that ancestor was a parent (1 generation ago), a grandparent (2 generations ago), or someone from even more generations ago. Help her out.

Being part Elf works the way you probably expect. Elves, Humans and part Elves are all created in the same way: two parents get together and have a baby. If one parent is A/B Elf and the other parent is C/D Elf, then their baby is (A/B + C/D) / 2 Elf. For example, the baby of a 0/1 Elf and a 1/2 Elf is 1/4 Elf.

Vida is certain about one thing: 40 generations ago she had $2^{40}$ different ancestors, and each one of them was 1/1 Elf or 0/1 Elf.

Vida says she is $P/Q$ Elf. Tell her the minimum number of generations ago that a 1/1 Elf could have been in her family. If it is not possible for her to be $P/Q$ Elf, tell her that she must be wrong.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains one fraction of the form $P/Q$, where $P$ and $Q$ are integers.

Limits

• $1 \le T \le 100$
• $1 \le P < Q \le 10^{12}$
• $P$ and $Q$ may share a common factor. $P/Q$ is not guaranteed to be in lowest terms.

For each test case, print one line in the form Case #x: y, where x is the test case number starting from 1 and y is the minimum number of generations ago a 1/1 Elf could have been in Vida's family if she is $P/Q$ Elf. If it is impossible for Vida to be $P/Q$ Elf, print impossible in place of y, without the quotes.

If $P/Q$ is 1/2, Vida could have a 1/1 Elf parent and a 0/1 Elf parent. A 1/1 Elf is then one generation ago, so the answer is 1.

If $P/Q$ is 3/4, Vida could have a 1/1 Elf parent and a 1/2 Elf parent. Again a 1/1 Elf is one generation ago, so the answer is 1.

If $P/Q$ is 1/4, Vida could have a 0/1 Elf parent and a 1/2 Elf parent. That 1/2 Elf parent could in turn be the baby of a 1/1 Elf and a 0/1 Elf. A 1/1 Elf is then two generations ago, so the answer is 2.

If $P/Q$ is 2/23, no family whose ancestors 40 generations ago were all 0/1 Elf or 1/1 Elf produces exactly 2/23 Elf, so the answer is impossible.

Vida does have a lot of ancestors. If that is the part of the problem that seems the most unrealistic to you, please re-read the part about Elves.