1	9057565540
2	880396204
3	221899096
4	90614180
5	47998942
6	32163167
7	23637993
8	19109994
9	16356034
10	14737519
11	13763406
12	13214140
13	12927025
14	12835684
15	12830714
16	12897873
17	13024151
18	13151811
19	13277069
20	13384003
21	13487422
22	13578991
23	13634623
24	13668407
25	13694005
26	13678605
27	13649774
28	13601549
29	13510327
30	13420437
31	13293073
32	13154774
33	13037237
34	12877722
35	12693500
36	12505593
37	12315566
38	12126179
39	11916455
40	11700147
41	11478712
42	11264367
43	11033112
44	10796003
45	10583673
46	10352287
47	10125851
48	9904722
49	9679058
50	9451673
51	9219547
52	9008972
53	8785758
54	8569155
55	8355181
56	8134384
57	7932472
58	7723199
59	7516257
60	7323575
61	7126672
62	6931473
63	6745270
64	6569611
65	6383389
66	6213242
67	6051873
68	5887809
69	5724393
70	5568929
71	5415000
72	5272800
73	5132104
74	4992930
75	4863030
76	4732288
77	4609253
78	4487448
79	4376108
80	4271443
81	4155726
82	4043867
83	3943286
84	3840015
85	3746666
86	3652882
87	3562046
88	3469731
89	3384852
90	3298847
91	3223058
92	3147890
93	3074363
94	3002575
95	2924062
96	2859394
97	2788069
98	2723129
99	2661384
100	2601452
101	2535505
102	2478119
103	2418769
104	2358728
105	2303976
106	2249709
107	2196807
108	2143070
109	2091716
110	2040091
111	1995426
112	1945710
113	1898972
114	1853970
115	1812326
116	1766858
117	1726781
118	1684713
119	1643547
120	1601002
121	1562936
122	1523189
123	1488859
124	1447560
125	1413859
126	1377827
127	1347173
128	1315423
129	1278234
130	1243720
131	1212315
132	1178188
133	1150259
134	1119576
135	1091136
136	1062784
137	1035775
138	1008231
139	979827
140	957810
141	934858
142	909297
143	886895
144	861951
145	841074
146	817719
147	795356
148	775992
149	755838
150	736911
151	715785
152	696014
153	678896
154	659998
155	642176
156	624194
157	607487
158	591947
159	577810
160	561401
161	547289
162	533436
163	520575
164	506118
165	494534
166	480810
167	469504
168	457723
169	446385
170	435697
171	425172
172	413317
173	404009
174	394256
175	383256
176	375356
177	366951
178	358781
179	349606
180	341874
181	332895
182	326108
183	319450
184	312789
185	306353
186	300075
187	291395
188	285670
189	278810
190	273504
191	267893
192	261839
193	256320
194	252361
195	248519
196	242005
197	237275
198	233339
199	228922
200	223581
201	219972
202	215402
203	211850
204	208054
205	203666
206	200666
207	196413
208	194022
209	190642
210	188081
211	185097
212	182030
213	178433
214	176297
215	174463
216	170874
217	168021
218	165169
219	163271
220	160865
221	158250
222	155827
223	154328
224	150971
225	149886
226	147334
227	145634
228	143907
229	142365
230	139896
231	138224
232	136001
233	134730
234	132380
235	131358
236	129036
237	127458
238	126184
239	124472
240	123243
241	122447
242	121289
243	119895
244	118592
245	117053
246	115371
247	114655
248	113317
249	111963
250	111516
251	110502
252	109464
253	108230
254	106892
255	106051
256	104799
257	104012
258	103333
259	102316
260	100609
261	100068
262	98890
263	97781
264	97227
265	96353
266	95506
267	94436
268	93804
269	92827
270	91398
271	90782
272	90123
273	89298
274	88678
275	87992
276	86715
277	86057
278	85908
279	85454
280	84692
281	83884
282	83570
283	82533
284	81785
285	81573
286	80519
287	79754
288	78699
289	78382
290	78052
291	76967
292	76744
293	75965
294	75772
295	75219
296	74157
297	73917
298	73099
299	73040
300	72330
301	72020
302	70978
303	70626
304	70540
305	69463
306	68993
307	68985
308	68161
309	67152
310	66892
311	66259
312	66128
313	65696
314	65202
315	64864
316	64382
317	64235
318	63222
319	64052
320	62232
321	62322
322	62029
323	61638
324	61478
325	60541
326	60752
327	59878
328	59596
329	59079
330	59066
331	58123
332	57614
333	57505
334	56647
335	56972
336	56695
337	56396
338	56249
339	55681
340	55607
341	54865
342	54726
343	54331
344	53979
345	53464
346	53101
347	53110
348	52447
349	51907
350	51957
351	51592
352	51493
353	50946
354	50458
355	50543
356	49780
357	50221
358	49698
359	49499
360	49145
361	48745
362	48262
363	47725
364	47575
365	47598
366	47710
367	47110
368	46959
369	46551
370	45926
371	45922
372	45962
373	46222
374	45863
375	45303
376	45258
377	44754
378	44313
379	44256
380	43805
381	43949
382	43298
383	43287
384	42812
385	42768
386	42573
387	42472
388	42284
389	42292
390	41787
391	41729
392	41487
393	41320
394	40780
395	40788
396	40347
397	39939
398	40216
399	39912
400	39592
401	39665
402	39362
403	39237
404	39105
405	38971
406	38312
407	38488
408	37981
409	37840
410	37519
411	37338
412	37458
413	37208
414	37025
415	36792
416	36970
417	37190
418	36910
419	36764
420	36300
421	36238
422	36004
423	35591
424	35455
425	35292
426	35356
427	34790
428	34777
429	34976
430	34516
431	34430
432	34170
433	34451
434	34044
435	34041
436	33842
437	33517
438	33413
439	33138
440	32722
441	32882
442	32691
443	32404
444	31969
445	32549
446	31799
447	31898
448	31922
449	31743
450	31674
451	31691
452	31361
453	31155
454	31083
455	30682
456	30585
457	30455
458	30467
459	30289
460	30231
461	30208
462	29925
463	29951
464	29930
465	29816
466	29458
467	29387
468	28987
469	29296
470	28928
471	28700
472	28777
473	28744
474	28890
475	28438
476	28271
477	28349
478	28480
479	28070
480	27987
481	28034
482	27515
483	27441
484	27668
485	27274
486	27371
487	26973
488	27075
489	27025
490	26896
491	27445
492	27162
493	26732
494	26841
495	26419
496	26811
497	26336
498	26432
499	26477
500	25935
501	26051
502	26189
503	25572
504	25838
505	25585
506	25431
507	25165
508	25222
509	25347
510	24991
511	24843
512	24893
513	24577
514	24805
515	24323
516	24367
517	24624
518	24227
519	24238
520	24203
521	24092
522	23722
523	24025
524	23616
525	23686
526	23349
527	23577
528	23492
529	22968
530	23180
531	23041
532	23185
533	22819
534	22915
535	22674
536	22357
537	22421
538	22316
539	22440
540	22298
541	22124
542	21979
543	21894
544	22062
545	21975
546	21970
547	21724
548	21777
549	21605
550	21589
551	21464
552	21545
553	21195
554	21421
555	21352
556	21222
557	21037
558	21191
559	20810
560	20943
561	20717
562	20802
563	20717
564	20498
565	20332
566	20256
567	20075
568	20212
569	19844
570	20060
571	19992
572	20031
573	19948
574	19830
575	19957
576	19666
577	19536
578	19762
579	19593
580	19487
581	19642
582	19461
583	19285
584	19130
585	19084
586	19281
587	19079
588	19130
589	19244
590	18991
591	18816
592	18883
593	18865
594	18689
595	18705
596	18784
597	18728
598	18520
599	18436
600	18444
601	18466
602	18244
603	18341
604	18153
605	18097
606	17944
607	17981
608	17765
609	17843
610	17753
611	17790
612	17951
613	17628
614	17916
615	17579
616	17613
617	17561
618	17370
619	17298
620	17427
621	16843
622	17191
623	17020
624	16860
625	17201
626	16946
627	16846
628	16660
629	16893
630	16427
631	16503
632	16432
633	16617
634	16650
635	16316
636	16318
637	16293
638	16296
639	16342
640	15820
641	16069
642	16030
643	16136
644	15989
645	15908
646	15990
647	15735
648	15594
649	15822
650	15838
651	15787
652	15612
653	15707
654	15709
655	15615
656	15525
657	15459
658	15487
659	15353
660	15395
661	15412
662	15400
663	15241
664	15131
665	14897
666	15145
667	15130
668	14883
669	14922
670	14806
671	14718
672	14855
673	14675
674	14533
675	14431
676	14576
677	14290
678	14542
679	14592
680	14535
681	14516
682	14272
683	14312
684	14714
685	14292
686	14216
687	14261
688	14048
689	14009
690	13909
691	14189
692	13869
693	14086
694	13957
695	13897
696	13968
697	13672
698	13750
699	13828
700	13506
701	13620
702	13680
703	13679
704	13598
705	13568
706	13488
707	13357
708	13407
709	13261
710	13475
711	13343
712	13031
713	13161
714	13198
715	13083
716	13118
717	12759
718	12877
719	13078
720	12821
721	12756
722	12894
723	12898
724	12717
725	12752
726	12498
727	12887
728	12705
729	12567
730	12607
731	12807
732	12603
733	12325
734	12554
735	12262
736	12478
737	12442
738	12351
739	12366
740	12229
741	12275
742	12029
743	12269
744	12060
745	12189
746	12020
747	11860
748	11799
749	12008
750	11975
751	11918
752	12113
753	11724
754	11812
755	11980
756	11833
757	11816
758	11489
759	11607
760	11518
761	11536
762	11361
763	11538
764	11471
765	11419
766	11368
767	11541
768	11320
769	11306
770	11410
771	11308
772	11423
773	11274
774	11207
775	11145
776	11380
777	11259
778	11219
779	11262
780	10977
781	11109
782	11041
783	11115
784	10916
785	10970
786	11143
787	11062
788	10799
789	11032
790	10950
791	10743
792	10753
793	10855
794	10830
795	10657
796	10744
797	10482
798	10650
799	10676
800	10634
801	10651
802	10505
803	10511
804	10494
805	10495
806	10136
807	10553
808	10305
809	10141
810	10118
811	10301
812	10222
813	10131
814	10059
815	10274
816	9926
817	10083
818	10222
819	10222
820	10197
821	9954
822	9943
823	9983
824	10001
825	10040
826	9880
827	9720
828	9866
829	9811
830	9890
831	9624
832	9605
833	9721
834	9766
835	9801
836	9877
837	9742
838	9586
839	9656
840	9689
841	9473
842	9593
843	9682
844	9654
845	9463
846	9606
847	9470
848	9444
849	9471
850	9404
851	9204
852	9225
853	9363
854	9339
855	9112
856	9230
857	9188
858	9147
859	9107
860	8894
861	9046
862	9004
863	8997
864	9001
865	8854
866	8935
867	8973
868	8854
869	9250
870	8903
871	8811
872	8947
873	8997
874	9093
875	8765
876	8853
877	8855
878	8934
879	8902
880	8710
881	8751
882	8620
883	8603
884	8756
885	8594
886	8775
887	8635
888	8623
889	8568
890	8581
891	8637
892	8487
893	8562
894	8721
895	8528
896	8535
897	8596
898	8433
899	8461
900	8391
901	8365
902	8275
903	8176
904	8345
905	8307
906	8128
907	8063
908	8165
909	8056
910	7977
911	7992
912	8216
913	8101
914	8062
915	8078
916	8027
917	7983
918	7979
919	7792
920	7934
921	7816
922	7937
923	7934
924	8002
925	7780
926	7820
927	7955
928	7830
929	7896
930	8013
931	7780
932	7895
933	7771
934	7920
935	7808
936	7693
937	7696
938	7712
939	7601
940	7774
941	7563
942	7633
943	7578
944	7583
945	7508
946	7444
947	7441
948	7436
949	7501
950	7399
951	7362
952	7387
953	7405
954	7343
955	7524
956	7279
957	7503
958	7316
959	7201
960	7223
961	7351
962	7312
963	7274
964	7267
965	7368
966	7207
967	7351
968	7176
969	7176
970	7284
971	7142
972	7201
973	7143
974	7071
975	7154
976	7015
977	6971
978	7025
979	7021
980	7011
981	6970
982	7071
983	7001
984	6843
985	6892
986	7090
987	6932
988	7005
989	6949
990	6731
991	6837
992	6731
993	6643
994	6888
995	6690
996	6722
997	6645
998	6761
999	6738
1000	23298614