Description

学校一年一度的"趣味数学节"开幕啦！今年的主题是「神奇的质数」。

参与活动的 n 位同学按照到场顺序领到了自己的号码牌，号码从 1 到 n 依次排列。活动组委会规定：拿到质数号码的同学可以获得一枚精美的"质数徽章"🎖️，并组队参加终极挑战。

小安是这次活动的志愿者，她想提前统计一下：到底有多少同学能拿到质数徽章？以及号码最大的那位"质数幸运儿"是谁呢？快来帮小安算一算吧！

质数（素数）定义：大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。例如 2、3、5、7、11 都是质数；而 4、6、9、15 不是质数。

Format

Input

一行，一个正整数 n，表示参与活动的同学总数。

数据范围：2 ≤ n ≤ 2×10⁶

Output

共两行：

第一行：一个整数，表示拿到质数号码的同学人数。

第二行：一个整数，表示质数号码中的最大值。

Samples

input1

10

output1

4
7

input2

20

output2

8
19

Limitation

500ms, 1024KiB for each test case.