Problem Statement

A positive integer $N$ is given as input.

For each positive integer $n$, let $F_n$ denote the $n$-th term of the Fibonacci sequence.

That is, $F_n$ is defined by the following recurrence:

$\displaystyle F_n = \left\{ \begin{array}{ll} 1 & (n = 1,2) \\ F_{n-1} + F_{n-2} & (n \geq 3) \end{array} \right. $

For any positive integer $n$, there exists a unique positive integer $m$ satisfying the following condition, and we denote it by $a(n)$:

• For any positive integer $k$, the following $2$ conditions are equivalent:
• $F_k$ is a multiple of $n$.
• $k$ is a multiple of $m$.

Find $a(N)$.

Background

This section explains the background for those familiar with category theory. In fact, the sequence $(a(n))_{n=1}^{\infty}$ can be characterized in the language of category theory. Define a small category $C$ by the following data:

• The set $\textrm{Ob}(C)$ of all objects of $C$ is the set of all positive integers.
• For each pair of positive integers $n$ and $m$, the set $\textrm{Hom}_C(n,m)$ of all morphisms $n \to m$ in $C$ is:
• the set $\{(n,m)\}$ consisting only of the pair $(n,m)$, if $m$ is a multiple of $n$;
• the empty set $\{\}$, if $m$ is not a multiple of $n$.
• For positive integers $n$, $m$, and $l$ and morphisms $f \colon n \to m$ and $g \colon m \to l$ in $C$, the composition $g \circ f$ in $C$ is the pair $(n,l)$.

It is known that $(F_n)_{n=1}^{\infty}$ and $(a(n))_{n=1}^{\infty}$ both define functors from $C$ to $C$, and the definition of $(a(n))_{n=1}^{\infty}$ is precisely the property called left adjointness of $(F_n)_{n=1}^{\infty}$.

Input

The input is given from standard input in $1$ line in the following format:

$N$

Constraints

The input satisfies the following constraints:

• $N$ is an integer satisfying $1 \leq N \leq 400$.

Output

Output $a(N)$ in $1$ line.

Print a newline at the end.

Sample

1

1

2

3

3

4

400

300