【模板】原根

题号：NC231471
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定整数 $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)$ 。

输入描述:

第一行：一个整数 ，表示数据组数。
接下来  行：每行两个整数 ，表示一组询问数据。
，，

输出描述:

对于每组数据：
第一行输出一个整数 ，表示  的原根个数，第二行输出  个数，按照题目描述中要求输出。
注意：即使 ，也需要输出一个空行。

示例1

输入

复制

输出

复制

说明

对于第  组数据，给出的  的所有原根都出现在输出中。

对于第  组数据， 的原根集合为 。

对于第  组数据， 的原根集合为 。

备注:

原题链接：https://www.luogu.com.cn/problem/P6091