SP25214 OHANIGAME - Ohani And The Game

有一天，Ohani 和她的朋友在玩一个游戏。游戏的规则如下： 1. 由 Ohani 先开始游戏，随后两人交替进行。 2. 游戏开始时，他们共同选择一个数字 $N$。 3. 选择完成后，取该数的绝对值，即 $N = |N|$ 或 $N = \text{abs}(N)$。 4. 游戏进行中，每位玩家在其回合中从 $N$ 的所有除数中选择一个 $X$，其中 $1 < X \leq N$，然后用 $N$ 除以 $X$。接下来的玩家继续重复此步骤，直至 $N$ 等于 1。 5. 当 $N$ 变为 1 时，游戏结束。 6. 无法进行下一步操作的玩家即为失败者。每位玩家都会采用最优策略进行游戏。 Ohani 和她的朋友玩了很久，渐渐感到无趣。突然，Ohani 灵机一动，想尝试寻找一种有趣的变化。她想找出从 $N$ 到 1 的路径中，能够不共享除 1 和 $N$ 外任何其他数字的最大路径数。 举例来说： 假设 $N = 20$。 有两条可能的路径：20->10->5->1 和 20->5->1，这两条路径都包含数字 5。 然而路径 20->10->1 和 20->4->2->1 除了 20 和 1 外，没有其他公共数字。 Ohani 于是想知道，究竟有多少种这样的路径。由于她编程能力有限，她希望你能帮她算出结果。

第一行输入一个整数 $T$，表示测试用例的数量（$T \leq 100000$）。 接下来的 $T$ 行中，每行包含一个整数 $N$（$|N| \leq 1000000$）。

对于每个测试用例，输出满足条件的路径数量。如果不能将 $N$ 化为 1，则输出 `Impossible`。 **本翻译由 AI 自动生成**