1	9851521772
2	933156661
3	403738916
4	216720633
5	120414672
6	78223229
7	51883824
8	39839016
9	30730091
10	25941300
11	21842594
12	19320862
13	17110694
14	15531965
15	14195849
16	13125742
17	12233839
18	11512186
19	10880154
20	10348565
21	9881565
22	9481964
23	9141986
24	8824327
25	8543955
26	8298670
27	8064769
28	7872771
29	7682077
30	7504465
31	7338161
32	7181710
33	7037424
34	6902114
35	6769369
36	6631261
37	6512031
38	6390323
39	6276306
40	6170332
41	6044738
42	5954597
43	5852937
44	5746946
45	5640654
46	5550641
47	5451833
48	5364281
49	5274033
50	5183708
51	5087728
52	4999278
53	4903863
54	4825132
55	4737063
56	4656976
57	4576487
58	4507570
59	4433670
60	4352507
61	4280837
62	4208076
63	4137499
64	4066502
65	3997564
66	3919197
67	3857394
68	3789345
69	3729245
70	3660149
71	3598855
72	3533583
73	3478598
74	3419373
75	3362346
76	3303668
77	3250055
78	3195877
79	3142676
80	3086400
81	3035661
82	2977885
83	2930455
84	2877204
85	2830114
86	2781438
87	2736566
88	2686054
89	2632968
90	2587520
91	2548680
92	2499904
93	2456435
94	2415086
95	2371246
96	2330482
97	2291151
98	2250374
99	2210964
100	2172968
101	2134739
102	2100615
103	2060306
104	2026871
105	1991738
106	1952415
107	1921044
108	1880952
109	1852224
110	1821060
111	1784696
112	1753769
113	1723315
114	1691594
115	1664850
116	1635095
117	1607270
118	1578333
119	1548256
120	1521682
121	1492124
122	1468294
123	1442047
124	1413097
125	1387166
126	1360743
127	1337709
128	1313221
129	1290276
130	1265645
131	1244450
132	1222416
133	1199807
134	1179068
135	1157100
136	1137472
137	1115064
138	1097902
139	1075485
140	1057367
141	1038635
142	1020390
143	999630
144	982006
145	965136
146	947668
147	928928
148	911434
149	895031
150	881413
151	864963
152	849117
153	833731
154	818625
155	805457
156	790374
157	776002
158	765164
159	751121
160	736952
161	722481
162	710749
163	697153
164	685794
165	674052
166	660723
167	651214
168	639980
169	626792
170	616550
171	605747
172	596166
173	586487
174	577746
175	567399
176	556559
177	548070
178	538498
179	531060
180	521169
181	512966
182	503965
183	495667
184	487702
185	479353
186	471903
187	465048
188	458167
189	450600
190	443023
191	433808
192	428628
193	421287
194	414657
195	408548
196	401724
197	393585
198	389985
199	384653
200	378769
201	372236
202	367453
203	360994
204	356496
205	350498
206	345389
207	340285
208	336185
209	332234
210	326165
211	320975
212	317154
213	311486
214	307917
215	302216
216	299169
217	295001
218	290854
219	287263
220	284535
221	279117
222	275180
223	273138
224	269128
225	265627
226	261589
227	258731
228	255489
229	252259
230	249085
231	246029
232	242938
233	238632
234	236784
235	233658
236	229417
237	227073
238	224098
239	221172
240	219064
241	216594
242	212910
243	211930
244	208423
245	206305
246	205088
247	202386
248	199367
249	198015
250	195084
251	192576
252	190185
253	189687
254	186715
255	185119
256	182747
257	180700
258	179632
259	177005
260	175265
261	173730
262	171536
263	169882
264	167905
265	165399
266	163779
267	161793
268	160223
269	158197
270	157657
271	155110
272	154541
273	152115
274	151277
275	149591
276	148856
277	147256
278	145580
279	144866
280	143391
281	142095
282	141045
283	138292
284	137588
285	135830
286	135543
287	135217
288	132738
289	130846
290	131257
291	129522
292	127972
293	127068
294	125850
295	124666
296	123092
297	123099
298	121349
299	119961
300	119334
301	117718
302	116816
303	116002
304	114739
305	113758
306	112690
307	111304
308	111148
309	109758
310	109489
311	108071
312	107820
313	106859
314	105504
315	104899
316	104318
317	104293
318	102332
319	102338
320	101196
321	100807
322	99661
323	98990
324	97961
325	97682
326	97056
327	95475
328	95682
329	95005
330	93941
331	93320
332	92217
333	91769
334	90797
335	90307
336	89780
337	88827
338	88387
339	88175
340	87470
341	86627
342	85771
343	85066
344	83929
345	84542
346	83408
347	82923
348	82702
349	81647
350	81572
351	80984
352	80630
353	79784
354	78826
355	78477
356	78407
357	77874
358	77796
359	77253
360	76196
361	76174
362	75666
363	74974
364	74699
365	74061
366	73494
367	72765
368	72527
369	71978
370	71427
371	70780
372	70408
373	70110
374	69501
375	69051
376	69195
377	68349
378	68304
379	67713
380	67301
381	66823
382	66280
383	66142
384	65462
385	64852
386	64089
387	64275
388	63539
389	63589
390	62805
391	62267
392	62067
393	62355
394	61936
395	61270
396	60924
397	60457
398	59952
399	59703
400	59672
401	59297
402	58480
403	58330
404	57828
405	58169
406	57996
407	57967
408	56720
409	56554
410	55774
411	56325
412	55495
413	56004
414	54763
415	54874
416	54675
417	54466
418	54409
419	53726
420	53097
421	52842
422	53105
423	52343
424	52202
425	52020
426	51577
427	51074
428	50864
429	50693
430	50759
431	50224
432	50001
433	49568
434	49377
435	49063
436	48999
437	48503
438	48047
439	48260
440	47822
441	47458
442	47271
443	47134
444	47222
445	46776
446	46703
447	46577
448	45900
449	45898
450	45711
451	45545
452	45325
453	45245
454	45012
455	44391
456	44531
457	43836
458	43605
459	43289
460	43154
461	42633
462	42774
463	42511
464	42428
465	41991
466	42181
467	41807
468	41764
469	41510
470	41101
471	41276
472	41007
473	41244
474	40552
475	40634
476	39859
477	40153
478	40095
479	39831
480	39327
481	39039
482	39206
483	38977
484	38653
485	38580
486	38542
487	38377
488	37922
489	38068
490	37887
491	37412
492	37490
493	37654
494	36987
495	37148
496	36742
497	36361
498	37032
499	36062
500	36009
501	35864
502	35999
503	35581
504	35515
505	35393
506	35200
507	34852
508	35041
509	34413
510	34675
511	34361
512	34406
513	34267
514	33966
515	33934
516	34052
517	33831
518	33543
519	33231
520	33463
521	32874
522	33149
523	32172
524	32609
525	32306
526	32441
527	32007
528	32095
529	32575
530	31873
531	31864
532	31564
533	31455
534	31454
535	31366
536	31283
537	31028
538	30992
539	30535
540	30717
541	30075
542	30111
543	29822
544	29875
545	30067
546	29634
547	29912
548	30064
549	29518
550	29617
551	29631
552	29347
553	29440
554	29176
555	29034
556	29026
557	28847
558	28471
559	28959
560	28668
561	28221
562	27904
563	28241
564	27947
565	27838
566	27619
567	27851
568	27658
569	27374
570	27379
571	27032
572	26997
573	26952
574	26811
575	26327
576	26874
577	26296
578	26273
579	26128
580	26260
581	25979
582	26487
583	26019
584	25700
585	25867
586	26021
587	25636
588	25641
589	25496
590	25388
591	25114
592	25606
593	24735
594	24971
595	24794
596	24694
597	24976
598	25127
599	24718
600	24457
601	24537
602	24256
603	24079
604	24067
605	23988
606	24035
607	24012
608	23795
609	23823
610	23858
611	23728
612	23640
613	23678
614	23650
615	23498
616	23270
617	23602
618	23175
619	22828
620	23162
621	22697
622	22780
623	22590
624	23013
625	22631
626	22374
627	22775
628	22279
629	22415
630	22188
631	22002
632	21770
633	21838
634	21707
635	21687
636	21633
637	21656
638	21581
639	21698
640	21391
641	21334
642	21149
643	21273
644	21080
645	20893
646	20932
647	21132
648	21105
649	20902
650	20866
651	20723
652	20872
653	20483
654	20650
655	20411
656	20462
657	20346
658	20231
659	20546
660	20384
661	20274
662	20171
663	19905
664	19774
665	19720
666	19845
667	19805
668	19825
669	19281
670	19564
671	19425
672	19263
673	19558
674	19443
675	19078
676	19229
677	19234
678	19227
679	18802
680	19258
681	18953
682	19131
683	18890
684	18707
685	18650
686	18944
687	18595
688	18502
689	18579
690	18323
691	18472
692	18300
693	18445
694	18253
695	18116
696	18057
697	17918
698	18037
699	18058
700	18107
701	17756
702	17751
703	17952
704	17374
705	17558
706	17620
707	17567
708	17320
709	17773
710	17469
711	17489
712	17655
713	17190
714	17323
715	17658
716	17236
717	17117
718	17315
719	17073
720	17227
721	17028
722	16833
723	16909
724	16604
725	16710
726	16626
727	16830
728	16411
729	16530
730	16412
731	16297
732	16281
733	16497
734	16225
735	16205
736	16133
737	16246
738	16118
739	16073
740	15961
741	15813
742	15781
743	15796
744	16158
745	15901
746	15790
747	15800
748	15598
749	15703
750	15493
751	15398
752	15692
753	15440
754	15475
755	15399
756	15533
757	15306
758	15386
759	15305
760	15542
761	15283
762	15158
763	15263
764	15028
765	14922
766	14990
767	15067
768	14871
769	15004
770	15009
771	14898
772	14942
773	14627
774	14695
775	14651
776	14686
777	14571
778	14595
779	14636
780	14425
781	14281
782	14269
783	14375
784	14038
785	14382
786	14502
787	14131
788	14119
789	14281
790	14336
791	14113
792	14059
793	14152
794	13844
795	13930
796	13887
797	13873
798	13770
799	13915
800	13758
801	13831
802	13924
803	13582
804	13814
805	13588
806	13413
807	13860
808	13694
809	13610
810	13495
811	13528
812	13361
813	13512
814	13186
815	13249
816	13153
817	13096
818	13205
819	13050
820	13071
821	12931
822	13193
823	13057
824	12842
825	13071
826	12905
827	12839
828	12781
829	12849
830	12810
831	12617
832	12811
833	12741
834	12681
835	12681
836	12730
837	12392
838	12562
839	12444
840	12447
841	12523
842	12626
843	12408
844	12516
845	12547
846	12528
847	12458
848	12323
849	12184
850	12169
851	12312
852	12262
853	12106
854	12057
855	12162
856	11946
857	12055
858	12144
859	12068
860	12050
861	11922
862	11932
863	12127
864	11731
865	11991
866	11869
867	11769
868	11878
869	11874
870	11714
871	11602
872	11625
873	11586
874	11597
875	11686
876	11807
877	11440
878	11594
879	11497
880	11277
881	11562
882	11285
883	11434
884	11298
885	11415
886	11343
887	11131
888	11487
889	11105
890	11170
891	11174
892	10919
893	11068
894	11172
895	10903
896	11016
897	11025
898	11087
899	11108
900	10867
901	11104
902	11149
903	10786
904	10724
905	10958
906	11064
907	10819
908	10957
909	10734
910	10789
911	10756
912	10779
913	10638
914	10581
915	10425
916	10682
917	10558
918	10433
919	10745
920	10352
921	10465
922	10624
923	10217
924	10363
925	10354
926	10370
927	10413
928	10470
929	10538
930	10615
931	10294
932	10194
933	10489
934	10471
935	10277
936	10247
937	10093
938	10168
939	10231
940	10086
941	10013
942	10130
943	9971
944	10031
945	9756
946	10016
947	9733
948	9817
949	10069
950	9778
951	9723
952	9697
953	9687
954	9910
955	9724
956	9816
957	9785
958	9814
959	9635
960	9748
961	9654
962	9559
963	9703
964	9609
965	9521
966	9700
967	9422
968	9478
969	9259
970	9571
971	9375
972	9509
973	9510
974	9570
975	9235
976	9352
977	9234
978	9348
979	9204
980	9355
981	9303
982	9204
983	9060
984	9352
985	9144
986	9354
987	9227
988	9221
989	9207
990	9103
991	9223
992	9146
993	9152
994	9058
995	9079
996	9051
997	8967
998	9116
999	8987
1000	64151661