Ridbit начинает с целого числа \(n\).
За одну операцию он может выполнить одну из следующих операций:
- разделить \(n\) на один из его собственных делителей, или
- вычесть \(1\) из \(n\), если \(n\) больше \(1\).
Собственным делителем числа называется любой делитель числа, кроме самого числа. Например, \(1\), \(2\), \(4\), \(5\) и \(10\) — это собственные делители \(20\), но само число \(20\) им не является.
Какое минимальное количество операций понадобится Ridbit, чтобы превратить \(n\) в \(1\)?
Выходные данные
Для каждого набора входных данных выведите минимальное необходимое число операций для превращения \(n\) в \(1\).
Примечание
Для наборов входных данных тестового примера \(n\) может быть превращено в \(1\), используя следующие операции:
\(1\)
\(2 \xrightarrow{} 1\)
\(3 \xrightarrow{} 2 \xrightarrow{} 1\)
\(4 \xrightarrow{} 2 \xrightarrow{} 1\)
\(6 \xrightarrow{} 2 \xrightarrow{} 1\)
\(9 \xrightarrow{} 3 \xrightarrow{} 2\xrightarrow{} 1\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1
2
3
4
6
9
|
0
1
2
2
2
3
|