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 \pmod{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 \pmod{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 \pmod{n}~ for some element ~x~ in ~\mathbb{Z}_n~, then ~py \equiv a \pmod{n}~ for some element ~y~ in ~\mathbb{Z}_n~ or ~pz \equiv b \pmod{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\%~ of the points, ~n~ is prime.

For an additional ~20\%~ of the points, ~n \le 15~.

For an additional ~20\%~ 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