奇怪的纸币

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

  大家都知道人民币的面值有1元,2元,5元。这是因为1、2、5三个都是质数,可以合理地组合成其他数字。其中除了8和9需要3个数字才能组合成功外, 10以内的其他数字都可以由1、2、5中的1个或者2个组合。另外,人民币因为配备了10,所以10-2=8,10-1=9,这就完美解决了8和9的问题。由此一来,10以内所有的数字都在2张人民币以内就可以得到解决。

小明忽然想到1、5、7也同样都是质数,那么用这些面值的纸币组成某个数最小需要多少张纸币呢?

Input

一个数字 n(1 <= n <= 100000)

Output

一个数字,代表最少需要多少张面值 1 或 5 或 7 的纸币构成。

Sample Input

10

Sample Output

2

Hint

Source

7989