Description

windy has learned a game.

For the $N$ numbers from $1$ to $N$, each number is mapped to a unique and different number from $1$ to $N$ (i.e., a permutation).

At the beginning, windy writes the numbers in order $1, 2, 3, \cdots, N$ in a row on paper.

Then, underneath this row, he writes their corresponding numbers.

Next, underneath the new row, he writes the numbers corresponding to that row.

He repeats this process until the sequence becomes $1, 2, 3, \cdots, N$ again.

For example: $1\ 2\ 3\ 4\ 5\ 6$.

The correspondence is: $1\to 2$, $2\to 3$, $3\to 1$, $4\to 5$, $5\to 4$, $6\to 6$.

windy operates as follows: 1 2 3 4 5 6 2 3 1 5 4 6 3 1 2 4 5 6 1 2 3 5 4 6 2 3 1 4 5 6 3 1 2 5 4 6 1 2 3 4 5 6

At this point, we have several rows of permutations of $1$ to $N$; in the example there are $7$ rows.

Now windy wants to know: over all possible correspondences, how many different possible numbers of rows are there.

Input Format

A single integer, $N$.

Output Format

A single integer, the number of possible row counts.

3

3

10

16

Hint

For $30\%$ of the testdata, $1 \le N \le 10$.

For $100\%$ of the testdata, $1 \le N \le 1000$.

Translated by ChatGPT 5