Description

陆历川住在北望村，村头的小卖部是陆历川经常去的地方，一天陆历川来到小卖部 老板：“买啥子呦？” 陆历川：“买锤子撒。” 老板：“啥子类型的锤子呦？” 吧啦吧啦一顿说，陆历川挑好了要买的锤子，一共是$4$块钱，但是这个小卖部的老板总是喜欢搞一些优惠。 今天的优惠方式是，收取的金额为该金额除了其自身以外的最大因子，因为陆历川可以分多次付款，所以他可以把这次的钱分两次付款 每次付款金额是$2$元，这样的话他就可以利用优惠，使自己花$2$元就可以买到锤子了。 现在陆历川想知道，给定任意金额，他最后最少要交多少钱给老板

Format

Input

输入金额$n(2 \leq n \leq 1e8)$

Output

题目要求

Samples

2
3
4

1
1
2