Description

聪聪在研究素数，可是为搞清一些素数究竟在素数集合中排名老几，伤透了脑筋。还是你帮他编个程序搞定吧，否则，他慢腾腾慢腾腾地数，数到什么时候去?!

Input

输入有正整数N（1≤N≤1000000）若干。

Output

运行结果每个数占1行，结果中的每个数是输入的正整数在素数集合中的排位。如果输入的不是素数（这太有可能了），那就输出一个0表示。

Sample

Input

2
6
4
5
13

Output

1
0
0
3
6

Source: qianneng