Description

By chance, Little Keke obtained a password box said to contain an ancient treasure map. The box can be opened by cracking the password, and the ancient symbols engraved on the back of the box serve as hints.

After painstaking deciphering, Little Keke discovered that these symbols describe a number and its relation to the password. Suppose this number is $n$, and the password is $x$. Then we have: the password $x$ is greater than or equal to $0$ and less than $n$, and the remainder of $x^2$ divided by $n$ is $1$. Little Keke knows there may be more than one $x$ that satisfies these conditions, so she must compute all such $x$; the correct password is among them. The computation is arduous—can you write a program to help?

Input Format

One line containing an integer $n$ ($1 \leq n \leq 2 \times 10^9$).

Output Format

Find all $x$ that satisfy the conditions described above. If no such $x$ exists, output a single line None. Otherwise, output these $x$ in increasing order, one per line.

12

1
5
7
11

Hint

Translated by ChatGPT 5