P13253 [GCJ 2014 #1C] Part Elf

Vida 说她是半精灵：她的祖先中至少有一个是精灵。但她不知道这个精灵是她的父母（1 代之前）、祖父母（2 代之前），还是更久远的祖先。帮她找找看吧！ 成为半精灵的方式大致与你想象的一样。精灵、人类以及半精灵的孩子都是通过两个父母结合而诞生的。如果一位父母的精灵血统是 $\frac{A}{B}$，另一位是 $\frac{C}{D}$，那么他们的孩子的精灵血统将是 $\frac{(A/B + C/D)}{2}$。例如，如果一个精灵血统是 $\frac{0}{1}$ 的人与一个精灵血统是 $\frac{1}{2}$ 的人生了孩子，那么这个孩子的精灵血统将是 $\frac{1}{4}$。 Vida 确信一点：在 40 代之前，她有 $2^{40}$ 位不同的祖先，而且每一位的精灵血统都是 $\frac{1}{1}$ 或 $\frac{0}{1}$。 Vida 说她的精灵血统是 $\frac{P}{Q}$。请告诉她，若她的精灵血统真的是 $\frac{P}{Q}$，那么她家族中最少多少代之前可能出现过一位 $\frac{1}{1}$ 的纯精灵祖先。如果不可能拥有精确为 $\frac{P}{Q}$ 的精灵血统，请告诉她这是不可能的！

输入的第一行是测试用例数量 $T$。接下来的 $T$ 行中，每行包含一个分数，格式为 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 均为整数。

对于每个测试用例，输出一行，格式为 `"Case #x: y"`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Vida 家族中最少多少代之前可能出现过一位 $\frac{1}{1}$ 的纯精灵祖先。如果 Vida 不可能拥有 $\frac{P}{Q}$ 的精灵血统，则 $y$ 应为字符串 `"impossible"`（不带引号）。

请注意，第五个样例数据并不满足 Small 数据集的限制。即使你未能正确解出它，也可能已经正确解决了 Small 数据集。 **样例解释** 在第一个样例中，Vida 可以拥有一位 $\frac{1}{1}$ 的父母和一位 $\frac{0}{1}$ 的父母。也就是说，她的家族中 1 代之前就可能有一位纯精灵祖先，因此答案是 $1$。 在第二个样例中，Vida 的父母可以是一个 $\frac{1}{1}$ 的精灵和一个 $\frac{1}{2}$ 的精灵。那么她的家族中也可以在 1 代之前出现纯精灵祖先，因此答案是 $1$。 在第三个样例中，Vida 的父母可以是一个 $\frac{0}{1}$ 的人类和一个 $\frac{1}{2}$ 的精灵。而这个 $\frac{1}{2}$ 的精灵父母可以是一个 $\frac{1}{1}$ 的精灵和一个 $\frac{0}{1}$ 的人类。那么家族中可能在 2 代之前出现纯精灵祖先，因此答案是 $2$。 在第四个样例中，如果你的 40 代祖先都只可能是 $\frac{0}{1}$ 或 $\frac{1}{1}$ 的精灵，那么精确拥有 $\frac{2}{23}$ 的精灵血统是不可能的。 **注意** 是的，Vida 的祖先非常之多。如果你觉得这个设定最不现实，请重新阅读有关精灵的部分。 ## 限制条件 - $1 \leq T \leq 100$。 ### Small 数据集（8 分） - 时间限制：~~60~~ 3 秒。 - $1 \leq P < Q \leq 1000$。 - $P$ 与 $Q$ 互质，即 $\frac{P}{Q}$ 是最简分数。 ### Large 数据集（12 分） - 时间限制：~~120~~ 5 秒。 - $1 \leq P < Q \leq 10^{12}$。 - $P$ 与 $Q$ 不一定互质，即 $\frac{P}{Q}$ 不一定是最简分数。 翻译由 ChatGPT-4o 完成