题目背景

图片来自于 Solara570 的 B 站视频 轻易相信简单直观的结论究竟有多危险？。

很久以前的某一天，小 A 在 B 站上无意间刷到了这个视频。视频中的无穷幂塔方程及其「简单直观，但暗藏陷阱」的解法令他影响深刻。

$$\Huge x ^ {x ^ {x ^ {x ^ {x}}}}$$

题目描述

如果小 A 是一个，一个一个一个毒瘤，他会让你求解套了十层甚至九层的幂塔方程，但他不是。

他想让你求解：

$$x ^ x\equiv D \pmod n$$

保证 $n$ 的最大质因子不超过 $10 ^ 5$，且 $D$ 与 $n$ 互质。

你需要保证得到的解 $x$ 为 $[0, 2 ^ {125}]$ 范围内的整数。若该范围内无解，输出 $-1$；若存在多解，输出任意一个。

多组测试数据。

输入格式

第一行一个整数 $S$，表示该测试点的 Subtask 编号。

第二行一个整数 $T$，表示数据组数。接下来 $T$ 组测试数据，每组数据形如：

• 第一行两个整数 $n, D$。
• 第二行若干递增的质数 $p_1, p_2, \cdots, p_k$，表示 $n$ 的所有质因子。

输出格式

输出 $T$ 行 $[-1, 2 ^ {125}]$ 范围内的整数。

0
10
7 4
7
16 3
2
6 1
2 3
144 5
2 3
2520 11
2 3 5 7
999999 2
3 7 11 13 37
22511 21795
22511
47067727606562827 30911969774113407
3083 13697 25747 43291
2147483648 2333333
2
675288511488360000 510472780110265817
2 3 5 7 11

25
11
1
101
4811
219871229
16139671
760913896873844308082367046696111
1221598821
24445987958110300438937

提示

「数据范围与约定」

本题采用捆绑测试。

• Subtask #1（5 points）：$n\leq 20$。
• Subtask #2（8 points）：$n\leq 400$。依赖 Subtask #1。
• Subtask #3（11 points）：$n$ 是质数，$T\leq 10 ^ 4$。
• Subtask #4（15 points）：$\mu(n) \neq 0$，$T\leq 100$。
• Subtask #5（9 points）：$\mu(n) \neq 0$，$T\leq 10 ^ 4$。依赖 Subtask #4。
• Subtask #6（13 points）：$n = p ^ k(p \in \mathrm{prime})$，$T\leq 100$。
• Subtask #7（7 points）：$n = p ^ k(p \in \mathrm{prime})$，$T\leq 10 ^ 4$。依赖 Subtask #3，#6。
• Subtask #8（6 points）：$n$ 的最大质因子不超过 $1064$。依赖 Subtask #2。
• Subtask #9（16 points）：$n\leq 10 ^ 9$，$T\leq 10 ^ 4$。
• Subtask #10（10 points）：无特殊限制。依赖 Subtask #5，#7，#8，#9。

对于 $100\%$ 的数据：

• $1\leq T\leq 4\times 10 ^ 4$。
• $2\leq n \leq 10 ^ {18}$。
• $1\leq D < n$，$D\perp n$。
• $2\leq p_1 < p_2 < \cdots < p_k \leq 10 ^ 5$。

「帮助与提示」

选手可以通过边读入边试除的方式判断何时停止读入 $n$ 的质因子。

「题目来源」

• Sweet Round 8 F
• Idea & Solution：demonlover923 & codecode。
• Tester：Alex_Wei。