Description

Given an integer $n$, find all of its primitive roots.

To reduce the amount of output, an output parameter $d$ is given. Suppose $n$ has $c$ primitive roots, and in increasing order they are $g_1,\ldots,g_c$. You only need to output $g_d,g_{2d},\ldots,g_{\lfloor\frac{c}{d}\rfloor\times d}$ in order.

If you do not know the definition of a primitive root, you may look it up yourself or read the definition below:

A positive integer $g$ is a primitive root of a positive integer $n$ if and only if $1\leq g\leq n-1$, and the multiplicative order of $g$ modulo $n$ is $\varphi(n)$.

Input Format

This problem contains multiple test cases.

The first line: an integer $T$, the number of test cases.

The next $T$ lines: each line contains two integers $n,d$, representing one query.

Output Format

For each test case:

Output an integer $c$ in the first line, which is the number of primitive roots of $n$. In the second line, output $\lfloor\dfrac{c}{d}\rfloor$ numbers as required in the statement.

Note: even if $\lfloor\dfrac{c}{d}\rfloor=0$, you still need to output an empty line.

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 

Hint

[Sample Explanation]

For test cases $1,2,4,6$, all primitive roots of the given $n$ appear in the output.

For test case $3$, the set of primitive roots of $25$ is $\{2,3,8,12,13,17,22,23\}$.

For test case $5$, the set of primitive roots of $9$ is $\{2,5\}$.

[Constraints]

For $100\%$ of the testdata, $1\leq T\leq 10$, $2\leq n\leq 10^6$, $1\leq d\leq 200$. It is guaranteed that the total number of output integers does not exceed $10^5$.

Translated by ChatGPT 5