問題文

整数 x が書かれたボールに対し、そのボールを叩くことによって以下の操作が行われます。

• x が素数でない場合：叩かれたボールを消滅させ、整数 a が書かれたボールと整数 b が書かれたボールを追加する。a, b は ab=x かつ a \geq 2, b \geq 2 を満たす整数から自由に選ぶことができる。
• x が素数である場合：なにも起こらない。

また、魔法を 1 回使うと、現在あるすべてのボールを同時に叩くことができます。一方、魔法を使う以外の手段でボールを叩くことはできません。

さて、整数 N が書かれたボールが 1 個だけあります。あなたは何回か魔法を使うことで、すべてのボールに書かれている数を素数にしたいです。最小で何回の操作を行う必要がありますか？

制約

• 2 \leq N \leq 10^{12}
• N は整数

入力例 1

42

出力例 1

2

はじめに、42 が書かれたボールがあります。魔法を使ってこのボールを叩くと、例えば以下の操作が行われます。

• 42 が書かれたボールを消滅させ、7 が書かれたボールと 6 が書かれたボールを追加する。

いま、それぞれ 6, 7 が書かれた 2 個のボールがあります。魔法を使ってこれらのボールを叩くと、以下の操作が行われます。

• 7 が書かれたボールを叩いても何も起こらない。
• 6 が書かれたボールを消滅させ、2 が書かれたボールと 3 が書かれたボールを追加する。

いま、それぞれ 2, 3, 7 が書かれた 3 個のボールがあります。これらはすべて素数であるため、2 回の魔法で条件を達成することができます。2 回より少ない回数で条件を達成することはできません。

入力例 2

48

出力例 2

3

例えば、下図の手順で操作を行うと、3 回の魔法ですべてのボールに書かれている数を素数にできます。

入力例 3

54

出力例 3

2

入力例 4

53

出力例 4

0

はじめから素数の場合は、魔法を使わずとも条件を満たしているため、0 を出力してください。