Problem F
Solution Pollution
Mathematics is facing a crisis. There are too many solutions, and not enough problems! You’ve come up with a new problem, but if it has too many solutions, it will simply contribute to the solution pollution! To solve your dilemma, you must find all of the solutions $x$ to this system of congruences:
\begin{align*} x-1& \equiv 0\pmod{m-1}\\ x(x-1)& \equiv 0\pmod{m(m-1)} \end{align*}For example, when $m=6$, the four solutions for $x$ are $1$, $6$, $16$ and $21$, e.g., $16$ is a solution because $5$ divides $15$ and $30$ divides $240$.
Input
The first line of input contains an integer $T$, where $1\le T\le 10^3$, denoting the number of test cases. The next $T$ lines each contain a single integer $m$, where $3\le m\le 10^{9}$.
Output
Each test case corresponds with a single line of output. For each test case $m$, display, in ascending order, all integers $x$ which are solutions to the given system of congruences and satisfy $1<x<m(m-1)$. You are not interested in the trivial solution $x=1$ because it is a solution regardless of the choice of $m$.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 4 6 130 1000000000 |
4 6 16 21 130 3355 5161 8386 8515 11740 13546 1000000000 212890624787109376 787109375212890625 |
