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:

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₀ … 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.

The input consists of at most 100 test cases. Each test case is a single line containing an integer m (1 < m < 10⁹).

For each test case output in a single line the average among a_i, rounded down.