「SWTR-8」幂塔方程

 图片来自于 Solara570 的 B 站视频 [轻易相信简单直观的结论究竟有多危险？](https://www.bilibili.com/video/BV1PW41177Vb)。 很久以前的某一天，小 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](https://www.luogu.com.cn/contest/73382) F - Idea & Solution：[demonlover923](https://www.luogu.com.cn/user/152997) & [codecode](https://www.luogu.com.cn/user/119526)。 - Tester：[Alex_Wei](https://www.luogu.com.cn/user/123294)。