Background

The image comes from Solara570’s Bilibili video How dangerous is it to believe simple and intuitive conclusions too easily?.

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.

Problem Description

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:

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.

Input Format

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 Format

Output $T$ lines, each being an integer in the range $[-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

Hint

"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 F.
• Idea & Solution: demonlover923 & codecode.
• Tester: Alex_Wei.

Update on 2025.5.30: For this problem, it is possible to have $p_k\leq 10 ^ {18}$.

Translated by ChatGPT 5