D. Налоги
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В стране, где старик Фунт сейчас проживает и занимается различными махинациями, крайне необычные правила вычисления подоходного налога. Так, Фунт, который за год заработал n (n ≥ 2) бурлей, должен уплатить налог, равный по величине максимальному делителю числа n (отличного от самого n, разумеется). Например, если n = 6, то Фунт должен уплатить 3 бурля, если n = 25, то 5 бурлей, а если n = 2, то 1 бурль.

Поскольку Фунт ещё не сидел при капитализме, то он решился на мошенничество. А именно, он собирается разбить исходное n на несколько частей n1 + n2 + ... + nk = n (значение k произвольно, в том числе допустимо k = 1) и уплатить налог за каждую часть отдельно. Чтобы мошенничество Фунта не было совсем уж очевидным, следует избегать частей, равных 1, то есть ni ≥ 2 для всех i от 1 до k.

Остап Бендер хочет знать, сколько денег минимально придется заплатить Фунту, если для уплаты налога он разобьёт изначальную сумму n на части оптимальным образом.

Входные данные

В первой строке входных данных записано единственное целое число n (2 ≤ n ≤ 2·109) — годовой доход Фунта, с которого следует уплатить налог.

Выходные данные

Выведите одно целое число — минимальное количество денег, которое придется платить старику Фунту, если он разбил исходную сумму на части оптимальным образом.

Примеры
Входные данные
4
Выходные данные
2
Входные данные
27
Выходные данные
3