该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

ZK先生现在居住在一个税收法律非常特殊的国家。ZK先生今年的总收入为 $n$（$n \geq 2$）人民币，他需要缴纳的税款等于 $n$ 的最大真约数（即不等于 $n$ 本身的最大约数）。例如，若 $n=6$，ZK需要支付 $3$ 人民币；若 $n=25$，他需要支付 $5$ 人民币；若 $n=2$，他只需支付 $1$ 人民币。

ZK先生是个投机取巧的人，他打算通过拆分收入来少缴税款。具体来说，他想将原本的 $n$ 分成若干部分 $n_1 + n_2 + ... + n_k = n$（$k$ 可以是任意值，包括 $k=1$），并分别计算每部分的税款。注意，每部分必须至少为 $2$ 人民币，即 $n_i \geq 2$。

ZK想知道，在最优的拆分方案下，最少需要支付多少税款。

输入输出格式

输入格式

输入仅包含一个整数 $n$（$2 \leq n \leq 2 \times 10^9$）。

输出格式

输出一个整数，表示最少需缴纳的税款。

输入输出样例 #1

输入 #1

4

输出 #1

2

输入输出样例 #2

输入 #2

27

输出 #2

3

提示

数据规模与约定

对于全部的测试点，保证（$2 \leq n \leq 2 \times 10^9$）。