题目描述

你有一个数组 $A = [a1, \, a2, \, \dots , \, an]$，该数组中的元素为 $1$ 或者是素数（$2$除外）。
现在给你一个整数$n \, (n>0)$，请你计算最少需要从数组 $A$ 中找到几个元素之和为 $n$。

输入格式

输入一个整数 $n \, (0<n<10^{9})$。

输出格式

输出一个数表示最少需要的元素个数。

样例

2

2

9

3