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$.


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}$.


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
6 16 21
130 3355 5161 8386 8515 11740 13546
1000000000 212890624787109376 787109375212890625
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 7.2Hard
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in