【模板】N 次剩余

题目描述

你需要解方程 $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$。

输入输出样例

输入样例 #1

2
3 531441 330750
5 304128 1

输出样例 #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$。