Funt 先生现在居住在一个有着非常具体税法的国家。先生的总收入这一年的Funt等于n(n≥2)个burles,他要缴纳的税额按n的最大除数计算(当然不等于n)。例如,如果 n = 6,则 Funt 必须支付 3 个伯尔,而如果 n = 25,他需要支付 5 个伯尔,如果 n = 2,他只需支付 1 个伯尔。
作为先生。 Funt是一个非常机会主义的人,他想欺骗一下。特别是,他想把最初的n分成几部分n1 + n2 + ... + nk = n(这里k是任意的,甚至k = 1也可以),并为每一部分分别纳税。他不能让某个部分等于 1,因为这会暴露他的身份。因此,对于从 1 到 k 的所有 i,条件 ni ≥ 2 应该成立。
Ostap Bender 想知道,如果 Funt 选择将 n 分成几部分的最佳方式,他必须支付多少钱(即最少)。
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 2·109) — 先生的一年总收入。芬特。
输出
打印一个整数 — 先生的最小可能数量。 Funt 必须缴纳税款。
示例
输入 #1
4
输出 #1
2
输入 #2
27
输出 #2
3