問題文

入力に正整数 $N$ が与えられます。

各正整数 $n$ に対し、フィボナッチ数列の第 $n$ 項を $F_n$ と表します。

すなわち $F_n$ は以下の漸化式で定義されます：

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

任意の正整数 $n$ に対し、次の条件を満たす正整数 $m$ が一意に存在し、それを $a(n)$ と置きます：

• 任意の正整数 $k$ に対し、以下の $2$ 条件は同値である：
• $F_k$ が $n$ の倍数である。
• $k$ が $m$ の倍数である。

$a(N)$ を求めてください。

背景

圏論を知っている人向けに背景を説明します。実は数列 $(a(n))_{n=1}^{\infty}$ は圏論の言葉を用いて特徴づけることができます。小圏 $C$ を以下のデータで定めます：

• $C$ の対象全体の集合 $\textrm{Ob}(C)$ は、正整数全体の集合である。
• 各正整数 $n$ と $m$ に対し、$C$ における射 $n \to m$ 全体の集合 $\textrm{Hom}_C(n,m)$ は、
• $m$ が $n$ の倍数であるならば組 $(n,m)$ のみからなる集合 $\{(n,m)\}$ である。
• $m$ が $n$ の倍数でないならば空集合 $\{\}$ である。
• 各正整数 $n$ と $m$ と $l$ と、$C$ における射 $f \colon n \to m$ と $g \colon m \to l$ に対し、$C$ における合成 $g \circ f$ は組 $(n,l)$ である。

この時 $(F_n)_{n=1}^{\infty}$ と $(a(n))_{n=1}^{\infty}$ はともに $C$ から $C$ への関手を定めることが知られており、$(a(n))_{n=1}^{\infty}$ の定義はまさに $(F_n)_{n=1}^{\infty}$ の左随伴性と呼ばれる性質そのものです。

入力

入力は次の形式で標準入力から $1$ 行で与えられます：

$N$

制約

入力は以下の制約を満たします：

• $N$ は $1 \leq N \leq 400$ を満たす整数である。

出力

$a(N)$ を $1$ 行に出力してください。

最後に改行してください。

サンプル

1

1

2

3

3

4

400

300