我已经是一只废桔了

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在古老而神秘的 409 实验室,住着一位史诗级长者,世人称之为「金桔」。

金桔能歌善舞,能说会道,能写伸展树,会敲自动机,口算微积分,心算大反演,区域赛虐遍全场,傲得了娇卖得了萌,实乃 ACM 界之集大成长者

最近,临近退役的金桔自觉体弱多衰,身子骨一日不如一日,常常自言自语道:“唉,我已经是一只废桔了...”。现在,他连基本的查找大于等于 n 的素数都不会了,为了冲 Final,他只能求助于你,你能帮助金桔吗?

Input

输入数据有多组(数据组数不超过 100000),到 EOF 结束。

每组数据输入一行,包含一个整数 n (0 <= n < 5000000)。

Output

对于每组数据,输出一行,包含用空格隔开的两个整数 i, v,表示大于或等于 n 的第一个素数的相关信息。其中 i 表示此素数是第几个素数,v 表示此素数是多少。

Sample Input

1
2
3
4
1024
2333

Sample Output

1 2
1 2
2 3
3 5
173 1031
345 2333

Hint

Source

【第六届ACM趣味编程循环赛 Round #3】bLue