题目描述

你需要解方程 $x^n\equiv k\pmod m$，其中 $x\in [0,m-1]$。

输入格式

第一行正整数 $T$ 为数据组数。

每组数据三个正整数 $n,m,k$。

输出格式

每组数据一或两行：

第一行为不同解的个数 $c$。

若 $c\neq 0$，接下来第二行共 $c$ 个整数，升序输出所有可能解，空格隔开。

数据保证 $\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

提示

对于 $100 \%$ 的数据，$1\le T\le 100$，$1\le n\le 10^9$，$0\le k \lt m\le 10^9$。

设 $m$ 的唯一分解形式为 $m=\prod_{i=1}^s p_i^{q_i}$，保证方程 $x^n\equiv k\pmod{p_i^{q_i}}$ 在 $[0,p_i^{q_i})$ 中的解数 $\le 10^6$。