P8457 "SWTR-8" Power Tower Equation

 The image comes from Solara570’s Bilibili video [How dangerous is it to believe simple and intuitive conclusions too easily?](https://www.bilibili.com/video/BV1PW41177Vb). One day long ago, A happened to come across this video on Bilibili. The infinite power tower equation in the video, and its “simple and intuitive, but full of traps” solution, left a deep impression on him. $$ \Huge x ^ {x ^ {x ^ {x ^ {x}}}} $$

If A were a “duliu” (dú liú, a nasty problem setter), he would make you solve a power tower equation with ten or even nine layers, but he is not. He wants you to solve: $$ x ^ x\equiv D \pmod n $$ It is guaranteed that the largest prime factor of $n$ does not exceed $10 ^ 5$, and $D$ is coprime with $n$. You must ensure that the solution $x$ you obtain is an integer in the range $[0, 2 ^ {125}]$. If there is no solution in this range, output $-1$. If multiple solutions exist, output any one. There are multiple test cases.

The first line contains an integer $S$, representing the Subtask ID of this test point. The second line contains an integer $T$, representing the number of test cases. Then follow $T$ test cases. Each test case is: - The first line contains two integers $n, D$. - The second line contains several increasing primes $p_1, p_2, \cdots, p_k$, representing all prime factors of $n$.

Output $T$ lines, each being an integer in the range $[-1, 2 ^ {125}]$.

**"Constraints and Conventions"** **This problem uses bundled tests**. - Subtask #1 (5 points): $n\leq 20$. - Subtask #2 (8 points): $n\leq 400$. Depends on Subtask #1. - Subtask #3 (11 points): $n$ is prime, $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$. Depends on 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$. Depends on Subtask #3, #6. - Subtask #8 (6 points): the largest prime factor of $n$ does not exceed $ 1064$. Depends on Subtask #2. - Subtask #9 (16 points): $n\leq 10 ^ 9$, $T\leq 10 ^ 4$. - Subtask #10 (10 points): no special restrictions. Depends on Subtask #5, #7, #8, #9. For $100\%$ of the testdata: - $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$. **"Help and Hints"** Contestants may determine when to stop reading prime factors of $n$ by trial dividing while reading. **"Source"** - [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). **Update on 2025.5.30**: For this problem, it is possible to have $p_k\leq 10 ^ {18}$. Translated by ChatGPT 5