题目描述

给定整数 $n$，求它的所有原根。

为了减小你的输出量，给出输出参数 $d$，设 $n$ 的所有原根有 $c$ 个，从小到大分别为 $g_1,\ldots,g_c$，你只需要依次输出 $g_d,g_{2d},\ldots,g_{\lfloor\frac{c}{d}\rfloor\times d}$。

如果你不了解原根的定义，可以自行查找资料或阅读下列定义：

正整数 $g$ 是正整数 $n$ 的原根，当且仅当 $1\leq g\leq n-1$，且 $g$ 模 $n$ 的阶为 $\varphi(n)$。

输入格式

本题包含多组数据。

第一行：一个整数 $T$，表示数据组数。

接下来 $T$ 行：每行两个整数 $n,d$，表示一组询问数据。

输出格式

对于每组数据：

第一行输出一个整数 $c$，表示 $n$ 的原根个数，第二行输出 $\lfloor\dfrac{c}{d}\rfloor$ 个数，按照题目描述中要求输出。

注意：即使 $\lfloor\dfrac{c}{d}\rfloor=0$，也需要输出一个空行。

6
2 1
4 1
25 2
36 1
9 6
18 1

1
1 
1
3 
8
3 12 17 23 
0

2

2
5 11 

提示

【样例解释】

对于第 $1,2,4,6$ 组数据，给出的 $n$ 的所有原根都出现在输出中。

对于第 $3$ 组数据，$25$ 的原根集合为 $\{2,3,8,12,13,17,22,23\}$。

对于第 $5$ 组数据，$9$ 的原根集合为 $\{2,5\}$。

【数据范围】

对于 $100\%$ 的数据，$1\leq T\leq 10$，$2\leq n\leq 10^6$，$1\leq d\leq 200$，保证输出的数的总个数不超过 $10^5$。