P5668 [Template] $n$-th Power Residue

You need to solve the equation $x^n\equiv k\pmod m$, where $x\in [0,m-1]$.

The first line contains a positive integer $T$, the number of test cases. Each test case contains three positive integers $n, m, k$.

For each test case, output one or two lines: The first line contains the number of distinct solutions $c$. If $c\neq 0$, then output a second line with $c$ integers, in increasing order, listing all possible solutions separated by spaces. It is guaranteed that $\sum c_i \le 10^6$.

For $100\%$ of the testdata, $1\le T\le 100$, $1\le n\le 10^9$, $0\le k \lt m\le 10^9$. Let the unique factorization of $m$ be $m=\prod_{i=1}^s p_i^{q_i}$. It is guaranteed that the number of solutions to $x^n\equiv k\pmod{p_i^{q_i}}$ in $[0,p_i^{q_i})$ is $\le 10^6$. Translated by ChatGPT 5