問題文

複数の候補者の中から $1$ 人を決める多数決を行います。

はじめ、候補者は $N$ 人います。多数決は以下のように進行します。

• $x$ 人の投票者が $1$ 人 $1$ 票をいずれかの候補者に投票する。
• 投票の結果によって次のいずれかに分岐する。
  • 最多得票者が $1$ 人の場合、多数決は成功となり、終了する。
  • 候補者全員が同票の場合、多数決は失敗となり、終了する。
  • それ以外の場合、最多得票者以外を候補者から取り除いて手順の最初からやり直す。

投票者の人数 $x$ は多数決の途中で変化しません。

各投票者の投票先によらず、多数決が必ず成功するような $2$ 以上の整数 $x$ の最小値を求めてください。

制約

• $2 \le N \le 10^{10}$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

出力

答えを $1$ 行に出力してください。最後に改行してください。

サンプル

サンプル1

2

3

$x=2$ の場合、$2$ 人の投票者の投票先が別れると失敗になります。
$x=3$ の場合、$3$ 人の投票者の投票先に関わらず最多得票者は必ず $1$ 人になります。

サンプル2

6

7