Note

この問題はAdvent Calendar Contest Advent Calendar 2015の1日目の問題として作られました。

問題文

このゲームはプレイヤーが1人で行う。
ゲームの目的はゲーム盤左上隅の1のマスからスタートし、以下の移動のルールを守りながら、Nのマスに到達することである。

移動のルール

• 十字方向に隣接しているマスにのみ移動できる。
• 素数の書かれたマスを通ってはならない。

2つの移動のルールを守って、1からNまで到達することができればプレイヤーの勝利である。

このゲームで使うゲーム盤は1からNの番号が順番に書かれたNマスで構成されている。
幅$W$高さ$\lfloor N/W\rfloor$のマスの塊の左下に、幅$N\mathrm{mod}W$高さ$1$のマスの塊がくっついた形をしている。
例としてN=9のとき、Wの値に応じて考えられるゲーム盤の一部を下に示す。

素数でない自然数Nが与えられます。
プレイヤーが勝利可能な最小の自然数Wを出力してください。

入力

N

$4\le N\le {10}^{24}$
$N$は素数でない。

出力

$W$
条件を満たす最小の$W$を一行で出力してください。最後に改行してください。

サンプル