背景

本题是 176 题的加强版，增强了测试数据，时间空间复杂度要求更高

说明

编一个程序，计算1-$n$范围内素数的个数

输入格式

包括多组数据。每组数据仅有一个整数$n$。输入以0结束

输出格式

对于每组数据输入，输出一行，为1-$n$（包括$n$）之间的素数的个数

样例

100000000
85353
23634563
54644
99999999
345676
78453353
5485654
56634535
346445
87515745
6845554
99999994
34535
47745456
6778433
12366566
56345356
678545
66743355
78433454
6788954
12346956
56856
34543355
784343
67843344
34545
69795475
546567
99999993
65445535
99999992
78545
99999991
0

5761455
8308
1485644
5561
5761455
29628
4584374
379877
3373865
29697
5081348
466784
5761455
3689
2873757
462522
810553
3357744
54939
3937554
4583295
463183
809300
5764
2120524
62789
3998602
3691
4106828
45059
5761455
3865309
5761455
7707
5761455

100000000
67789999
88888888
88888888
99999999
78954885
69875555
88888888
0

5761455
3995674
5156463
5156463
5761455
4611989
4111240
5156463

提示

每个测试点数据个数比较多，数字比较大

数据范围

• $1\leqslant n\leqslant 10^{8}$
• 每个测试点数据个数$\leqslant $81