Description

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

Input Format

The first line contains a positive integer $T$, the number of test cases.

Each test case contains three positive integers $n, m, k$.

Output Format

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$.

2
3 531441 330750
5 304128 1

27
264 19947 39630 59313 78996 98679 118362 138045 157728 177411 197094 216777 236460 256143 275826 295509 315192 334875 354558 374241 393924 413607 433290 452973 472656 492339 512022
5
1 82945 138241 165889 193537

Hint

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