Willson is sad because nobody likes him.

Willson the Canada Goose is like any other Canada Goose - he suspects that many humans don't like him.

As a result, he challenges you to do the following problem:

Consider the set ${\mathbb{Z}}_n=\{0,1,2,\dots ,n-1\}$.

We say that an element $u$ in ${\mathbb{Z}}_n$ is a unit if there is some element $v$ in ${\mathbb{Z}}_n$ with $uv\equiv 1(\mathrm{mod}n)$.

We say that a non-zero, non-unit element $i$ in ${\mathbb{Z}}_n$ is irreducible if there are no elements $a,b$ in ${\mathbb{Z}}_n$ where $a,b$ are not units and $ab\equiv i(\mathrm{mod}n)$.

We say that a non-zero, non-unit element $p$ in ${\mathbb{Z}}_n$ is prime if for all elements $a,b$ in ${\mathbb{Z}}_n$, if $px\equiv ab(\mathrm{mod}n)$ for some element $x$ in ${\mathbb{Z}}_n$, then $py\equiv a(\mathrm{mod}n)$ for some element $y$ in ${\mathbb{Z}}_n$ or $pz\equiv b(\mathrm{mod}n)$ for some element $z$ in ${\mathbb{Z}}_n$.

Given $n$, please output all of the units, irreducibles, and primes of ${\mathbb{Z}}_n$.

Input Specification

The only line of input will contain a single integer, $n$ $(2\le n\le 200)$.

For $20\mathrm{\%}$ of the points, $n$ is prime.

For an additional $20\mathrm{\%}$ of the points, $n\le 15$.

For an additional $20\mathrm{\%}$ of the points, $n\le 50$.

Output Specification

Output, in numerical order, first the units, then the irreducibles, then the primes of ${\mathbb{Z}}_n$. See the Sample Output for more specific formatting.

Sample Input 1

10

Sample Output 1

Units:
1
3
7
9
Irreducibles:
Primes:
2
4
5
6
8

Sample Input 2

12

Sample Output 2

Units:
1
5
7
11
Irreducibles:
2
10
Primes:
2
3
9
10