C. 你们要的与质数与偶数相关的送分题 - 2018.1.29 新生训练 (Week 2) - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

给任意一个大于 $1$ 的正整数 $N$,输出 $N$ 可以分解成最少几个质数(可以相同)的和。

输入格式

一行，一个整数 $N$。$(2\le N\le 10^{15})$

输出格式

一行一个数，代表 $N$ 最少能分解成几个质整数。

样例

Input

Output

提示

这不仅仅是一道水题，它甚至还是一道CF原题。

A. 算数 B. 归零 C. 你们要的与质数与偶数相关的送分题 D. 说出来可能不信这是排序题 E. 简单排序题 F. 这也是一道排序题

题目	计分
A	100
B	100
C	100
D	100
E	100
F	100

这里显示的是你在现在一次提交正确所获得的计分。