Once Sasha decided that a random shuffler in his favourite media player
should be replaced. Sasha wants to calculate the order of songs according
to the following rule:
x_{0} = 0,
x_{i} = (x_{i − 1} · a + b) mod m,
where
m is the total number of songs,
a and
b are integers in range from 0 to
m − 1.
Generated sequence of song numbers should satisfy the following rules:
 x_{0} … x_{m − 1} should be a permutation of integers from 0 to m − 1,
 x_{m} should be equal to zero.
Sasha wants to find all pairs (
a_{i},
b_{i}), resulting in a valid sequences and calculate the average among all
a_{i}. Help him do it.
Input
The input consists of at most 100 test cases. Each test case is a single line containing an integer m (1 < m < 10^{9}).
Output
For each test case output in a single line the average among a_{i}, rounded down.
Sample
input  output 

2
36
100
123
 1
13
41
1

Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010.