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$ 精灵。请告诉她，她的家族中出现 $1/1$ 精灵的最短代数是多少。如果她不可能成为 $P/Q$ 精灵，请告诉她她一定弄错了！

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 行，每行包含一个分数 $P/Q$，其中 $P$ 和 $Q$ 为整数。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是如果她是 $P/Q$ 精灵，其家族中出现 $1/1$ 精灵的最短代数。如果 Vida 不可能是 $P/Q$ 精灵，则 $y$ 应为字符串 "impossible"。

数据范围

$1 \le T \le 100$。

小数据集

$1 \le P < Q \le 1000$。 $P$ 和 $Q$ 没有公因数。这意味着 $P/Q$ 是最简分数。

大数据集

$1 \le P < Q \le 10^{12}$。 $P$ 和 $Q$ 可能有公因数。$P/Q$ 不保证是最简分数。

样例

样例输入 1

5
1/2
3/4
1/4
2/23
123/31488

样例输出 1

Case #1: 1
Case #2: 1
Case #3: 2
Case #4: impossible
Case #5: 8

注意，第五个样例不符合小数据集的范围。即使你没有正确解决它，你可能仍然正确解决了小数据集。

说明

在第一个样例中，Vida 可能有一位 $1/1$ 精灵父母和一位 $0/1$ 精灵父母。这意味着她可能在 1 代前就有一位 $1/1$ 精灵祖先，所以答案是 1。

在第二个样例中，Vida 可能有一位 $1/1$ 精灵父母和一位 $1/2$ 精灵父母。这意味着她可能在 1 代前就有一位 $1/1$ 精灵祖先，所以答案是 1。

在第三个样例中，Vida 可能有一位 $0/1$ 精灵父母和一位 $1/2$ 精灵父母。这位 $1/2$ 精灵父母可能有一位 $1/1$ 精灵父母和一位 $0/1$ 精灵父母。这意味着她可能在 2 代前就有一位 $1/1$ 精灵祖先，所以答案是 2。

在第四个样例中，如果 40 代前的祖先全都是 $0/1$ 精灵或 $1/1$ 精灵，则不可能恰好是 $2/23$ 精灵。

说明

是的，Vida 有很多祖先。如果这是你觉得问题中最不现实的部分，请重新阅读关于精灵的部分。