1	6174100464
2	1083340810
3	328907703
4	137093060
5	62242251
6	36628986
7	23361990
8	17090020
9	13187860
10	10843272
11	9240220
12	8142427
13	7346503
14	6757672
15	6322367
16	5993087
17	5738179
18	5528454
19	5369392
20	5234469
21	5119315
22	5033158
23	4960019
24	4886798
25	4825385
26	4778612
27	4739733
28	4691973
29	4647001
30	4602312
31	4565191
32	4528001
33	4494032
34	4459354
35	4415919
36	4371531
37	4328263
38	4291804
39	4258675
40	4227942
41	4193205
42	4150025
43	4106112
44	4068908
45	4028741
46	3988770
47	3948278
48	3913936
49	3879309
50	3841017
51	3801492
52	3768023
53	3728678
54	3697471
55	3655402
56	3624882
57	3588089
58	3554206
59	3518402
60	3478235
61	3442011
62	3406729
63	3361736
64	3331740
65	3295170
66	3261809
67	3229053
68	3193078
69	3162691
70	3123176
71	3091926
72	3057548
73	3027808
74	2986123
75	2957644
76	2920540
77	2890011
78	2861721
79	2830109
80	2802953
81	2776879
82	2746671
83	2714171
84	2679725
85	2648662
86	2621965
87	2591054
88	2561558
89	2541416
90	2504423
91	2477335
92	2451449
93	2426004
94	2399954
95	2374464
96	2342190
97	2322787
98	2299250
99	2275013
100	2250992
101	2227168
102	2199743
103	2175970
104	2148689
105	2126093
106	2104666
107	2080532
108	2055395
109	2034842
110	2013754
111	1991013
112	1970761
113	1944509
114	1923833
115	1905115
116	1885135
117	1862001
118	1847073
119	1827390
120	1809369
121	1785282
122	1768703
123	1746397
124	1729781
125	1711287
126	1696978
127	1679239
128	1661667
129	1644685
130	1628608
131	1612190
132	1595214
133	1577233
134	1558453
135	1546072
136	1525146
137	1511144
138	1496513
139	1480898
140	1459883
141	1448208
142	1431274
143	1419001
144	1403083
145	1390653
146	1372927
147	1361456
148	1343717
149	1331320
150	1317405
151	1302583
152	1288114
153	1279047
154	1265046
155	1252403
156	1239005
157	1225973
158	1214180
159	1201358
160	1188008
161	1177738
162	1163541
163	1151914
164	1139419
165	1127610
166	1113308
167	1102341
168	1093733
169	1082669
170	1069510
171	1059285
172	1048188
173	1034953
174	1024219
175	1015367
176	1003455
177	996046
178	983985
179	973967
180	963823
181	952640
182	944171
183	935638
184	925748
185	916331
186	905906
187	895885
188	885941
189	875963
190	867587
191	861113
192	851466
193	840170
194	829801
195	823502
196	814172
197	804499
198	796091
199	788437
200	780689
201	769766
202	762643
203	756017
204	746392
205	738279
206	730481
207	722759
208	715935
209	707579
210	700715
211	692999
212	686707
213	677383
214	669114
215	663185
216	655769
217	651212
218	643118
219	637480
220	630451
221	624954
222	618084
223	611468
224	602469
225	597470
226	592188
227	584595
228	578274
229	571399
230	566292
231	558854
232	553189
233	546180
234	540987
235	534702
236	528378
237	523233
238	516954
239	510786
240	505967
241	500876
242	495625
243	488434
244	483826
245	479826
246	476300
247	468564
248	463949
249	459558
250	453250
251	448886
252	443022
253	439674
254	434460
255	428950
256	425082
257	421333
258	416627
259	412052
260	405664
261	403070
262	398360
263	393658
264	388773
265	386852
266	381906
267	378558
268	374467
269	370102
270	367292
271	362099
272	359243
273	354072
274	350369
275	346997
276	342671
277	339437
278	335852
279	331389
280	328024
281	323023
282	320711
283	316059
284	312585
285	309417
286	306560
287	303699
288	300714
289	298144
290	294529
291	290769
292	289071
293	284320
294	280771
295	278245
296	275249
297	273548
298	269694
299	267722
300	264778
301	260729
302	259332
303	255553
304	254083
305	249769
306	248406
307	246026
308	243150
309	240731
310	238441
311	236244
312	233592
313	231362
314	228683
315	226266
316	222948
317	221068
318	218071
319	215378
320	213317
321	211652
322	209092
323	206860
324	204161
325	202385
326	200608
327	197988
328	197307
329	194689
330	192617
331	190679
332	188987
333	187026
334	184487
335	183322
336	181478
337	179896
338	176903
339	175686
340	173869
341	172363
342	169276
343	168879
344	167091
345	165263
346	162953
347	162290
348	159600
349	157643
350	156518
351	154593
352	152686
353	151679
354	150618
355	149030
356	148085
357	146373
358	144879
359	144653
360	142849
361	140388
362	139851
363	138400
364	137319
365	136014
366	134431
367	132495
368	131730
369	130127
370	129674
371	128225
372	127208
373	126022
374	125311
375	123554
376	122629
377	121380
378	120856
379	118778
380	117996
381	117136
382	115793
383	114355
384	113439
385	112652
386	111852
387	110144
388	108980
389	108284
390	107736
391	106621
392	105857
393	105020
394	104160
395	103049
396	101828
397	101414
398	100212
399	99683
400	98887
401	97991
402	96506
403	96167
404	94864
405	94210
406	92672
407	92262
408	91444
409	90574
410	89414
411	88842
412	88014
413	86812
414	86008
415	85895
416	85037
417	84339
418	83484
419	82833
420	81620
421	81307
422	80110
423	79796
424	79229
425	77978
426	77339
427	76187
428	76285
429	75694
430	75141
431	74251
432	73500
433	72358
434	72473
435	71465
436	71549
437	70738
438	69741
439	69209
440	69012
441	68634
442	68017
443	67292
444	66737
445	65921
446	66204
447	65483
448	64892
449	64083
450	63806
451	63122
452	62687
453	62112
454	62041
455	60901
456	60807
457	60471
458	59745
459	59481
460	59056
461	58973
462	58040
463	57492
464	56963
465	57239
466	56106
467	56334
468	55221
469	55337
470	54701
471	54024
472	53971
473	53457
474	52970
475	52771
476	52328
477	52124
478	51377
479	50862
480	50560
481	49736
482	49593
483	49058
484	49068
485	47988
486	47929
487	47504
488	46521
489	46415
490	46701
491	46364
492	45676
493	45321
494	45703
495	44937
496	44542
497	44467
498	43732
499	43836
500	43288
501	42798
502	42803
503	42566
504	41826
505	41245
506	41132
507	41117
508	41112
509	40781
510	40793
511	39884
512	39779
513	39225
514	39148
515	38442
516	38636
517	38413
518	38147
519	37759
520	37268
521	37270
522	36585
523	37290
524	36686
525	35604
526	35809
527	35588
528	35268
529	35007
530	35136
531	34676
532	34465
533	34032
534	33963
535	33778
536	33253
537	33205
538	33061
539	32807
540	32666
541	32347
542	31937
543	31900
544	31619
545	31412
546	31101
547	30742
548	30853
549	30387
550	29889
551	30249
552	29710
553	29732
554	29477
555	29417
556	29214
557	28757
558	28810
559	28574
560	28429
561	28181
562	27921
563	27437
564	27306
565	26882
566	26969
567	26742
568	26921
569	26257
570	26646
571	26262
572	26097
573	26065
574	25848
575	25950
576	25467
577	25098
578	25114
579	24997
580	24896
581	24944
582	24518
583	24509
584	24299
585	23907
586	23786
587	24073
588	23647
589	23805
590	23667
591	23473
592	23224
593	23286
594	22892
595	22592
596	22688
597	22107
598	22104
599	22232
600	22309
601	21807
602	21472
603	21364
604	20906
605	21191
606	21101
607	21110
608	20898
609	20862
610	20526
611	20385
612	20525
613	20188
614	20451
615	20015
616	20019
617	19810
618	19528
619	19542
620	19420
621	19362
622	19383
623	19211
624	19061
625	18844
626	18812
627	18731
628	18709
629	18665
630	18950
631	18801
632	18505
633	18468
634	18332
635	18101
636	18013
637	17813
638	17853
639	17503
640	17167
641	17565
642	17192
643	17119
644	17137
645	17035
646	16826
647	16908
648	16920
649	16639
650	16571
651	16299
652	16272
653	16303
654	15929
655	15948
656	16004
657	16109
658	15638
659	15907
660	15581
661	15602
662	15409
663	15467
664	15475
665	15626
666	15151
667	15301
668	15111
669	14943
670	14931
671	15077
672	15054
673	14916
674	14764
675	14640
676	14532
677	14581
678	14604
679	14562
680	14571
681	14322
682	14420
683	14054
684	13930
685	13940
686	13904
687	13740
688	13714
689	13496
690	13407
691	13615
692	13710
693	13360
694	13542
695	13293
696	13211
697	13291
698	13400
699	13217
700	12996
701	13205
702	12819
703	12884
704	12791
705	12706
706	12799
707	12768
708	12711
709	12565
710	12399
711	12404
712	12496
713	12045
714	12398
715	12239
716	12148
717	12111
718	11788
719	12058
720	11884
721	12001
722	11812
723	11750
724	11837
725	11619
726	11598
727	11524
728	11516
729	11549
730	11344
731	11511
732	11360
733	11330
734	11129
735	11238
736	11241
737	11119
738	10966
739	10991
740	10901
741	10788
742	10746
743	10804
744	10545
745	10792
746	10730
747	10704
748	10539
749	10393
750	10467
751	10448
752	10461
753	10293
754	10313
755	10246
756	10296
757	10286
758	10167
759	10133
760	10102
761	9961
762	9972
763	10018
764	9974
765	10003
766	9930
767	9802
768	9984
769	10005
770	10002
771	9879
772	9891
773	9802
774	9723
775	9722
776	9721
777	9669
778	9535
779	9451
780	9436
781	9561
782	9452
783	9602
784	9294
785	9329
786	9248
787	9256
788	9037
789	9320
790	9247
791	9200
792	9123
793	9048
794	9168
795	9150
796	9115
797	9018
798	8851
799	8960
800	8987
801	8917
802	8887
803	8955
804	8839
805	8805
806	8714
807	8797
808	8651
809	8589
810	8760
811	8588
812	8642
813	8633
814	8529
815	8683
816	8544
817	8492
818	8607
819	8509
820	8418
821	8247
822	8356
823	8306
824	8384
825	8355
826	8249
827	8347
828	8353
829	8204
830	8101
831	8118
832	8085
833	8153
834	8009
835	7882
836	8236
837	7966
838	7981
839	7827
840	8161
841	7978
842	7955
843	7906
844	7936
845	7900
846	7805
847	7806
848	7819
849	7706
850	7779
851	7749
852	7563
853	7567
854	7522
855	7788
856	7535
857	7720
858	7454
859	7556
860	7398
861	7431
862	7427
863	7614
864	7492
865	7210
866	7457
867	7283
868	7320
869	7328
870	7183
871	7235
872	7088
873	7172
874	7322
875	7120
876	7138
877	7100
878	6960
879	6994
880	7079
881	7076
882	7052
883	7121
884	6987
885	7004
886	6984
887	7138
888	6823
889	6968
890	6948
891	6971
892	6815
893	6766
894	6844
895	6770
896	6967
897	6636
898	6749
899	6853
900	6664
901	6724
902	6630
903	6884
904	6716
905	6645
906	6571
907	6674
908	6727
909	6581
910	6594
911	6508
912	6724
913	6489
914	6417
915	6391
916	6346
917	6470
918	6255
919	6413
920	6442
921	6353
922	6425
923	6220
924	6356
925	6252
926	6323
927	6301
928	6393
929	6215
930	6262
931	6249
932	6150
933	6063
934	6220
935	6065
936	6169
937	6239
938	6041
939	6188
940	6086
941	5996
942	6213
943	5993
944	6011
945	6015
946	6165
947	6130
948	6005
949	6017
950	6005
951	5859
952	5850
953	5890
954	6012
955	5893
956	5813
957	5776
958	5889
959	5756
960	5900
961	5904
962	5943
963	5773
964	5799
965	5844
966	5894
967	5803
968	5653
969	5767
970	5742
971	5729
972	5782
973	5710
974	5811
975	5583
976	5603
977	5632
978	5690
979	5514
980	5719
981	5594
982	5601
983	5610
984	5552
985	5520
986	5549
987	5493
988	5498
989	5475
990	5486
991	5505
992	5320
993	5461
994	5516
995	5470
996	5318
997	5398
998	5321
999	5301
1000	28143763