1	5610847577
2	902296946
3	367398232
4	203055317
5	130198152
6	90043571
7	65442356
8	49907199
9	39563839
10	32690542
11	27709342
12	24231382
13	21388166
14	19096489
15	17142858
16	15531507
17	13960049
18	12583721
19	11416939
20	10336081
21	9411899
22	8671585
23	7948269
24	7334697
25	6694606
26	6189727
27	5713883
28	5293680
29	4893768
30	4516087
31	4159122
32	3854503
33	3601170
34	3363361
35	3155728
36	2971116
37	2809398
38	2670908
39	2580857
40	2524759
41	2469563
42	2440266
43	2397079
44	2384364
45	2360553
46	2362586
47	2362752
48	2362150
49	2362980
50	2368330
51	2368099
52	2366525
53	2374494
54	2385074
55	2392773
56	2404726
57	2425817
58	2450938
59	2458770
60	2474713
61	2490739
62	2492572
63	2509654
64	2526695
65	2536535
66	2536975
67	2540780
68	2552074
69	2553128
70	2568521
71	2566175
72	2563081
73	2564929
74	2573565
75	2563032
76	2574006
77	2576501
78	2581950
79	2585447
80	2577987
81	2581111
82	2591132
83	2588208
84	2594775
85	2587898
86	2595457
87	2588896
88	2592225
89	2588045
90	2591086
91	2578155
92	2581634
93	2578399
94	2575719
95	2558374
96	2550262
97	2542425
98	2522105
99	2496557
100	2477251
101	2459871
102	2446579
103	2428435
104	2404306
105	2388015
106	2354634
107	2328785
108	2298478
109	2271658
110	2247454
111	2229868
112	2210313
113	2175995
114	2153866
115	2125374
116	2101491
117	2077676
118	2060494
119	2051179
120	2028612
121	2012768
122	2000240
123	1993426
124	1988105
125	1968130
126	1956419
127	1946478
128	1951895
129	1942779
130	1934662
131	1931574
132	1926222
133	1925149
134	1931189
135	1929790
136	1939863
137	1943037
138	1950739
139	1942097
140	1952699
141	1957900
142	1960245
143	1957171
144	1961063
145	1956200
146	1957946
147	1971982
148	1984687
149	1997795
150	2004415
151	2018103
152	2018590
153	2029093
154	2031329
155	2037284
156	2037066
157	2035092
158	2046393
159	2046669
160	2046581
161	2048105
162	2049332
163	2052226
164	2060393
165	2061053
166	2067363
167	2068261
168	2072744
169	2077420
170	2075005
171	2075361
172	2076051
173	2070844
174	2071910
175	2065226
176	2066354
177	2069556
178	2067288
179	2062831
180	2058431
181	2053775
182	2048645
183	2047748
184	2048357
185	2037521
186	2035440
187	2025630
188	2028486
189	2018567
190	2014934
191	2000567
192	1995726
193	1987706
194	1983037
195	1978693
196	1971252
197	1965210
198	1952500
199	1945544
200	1935920
201	1926535
202	1923685
203	1918191
204	1901076
205	1883093
206	1875756
207	1862185
208	1848569
209	1847932
210	1843796
211	1830263
212	1817684
213	1813010
214	1806292
215	1793798
216	1781842
217	1772922
218	1764362
219	1761001
220	1750637
221	1744737
222	1739850
223	1725999
224	1713935
225	1712243
226	1698695
227	1695620
228	1687636
229	1680917
230	1670380
231	1659549
232	1642860
233	1640199
234	1631502
235	1618043
236	1606122
237	1601350
238	1592480
239	1582446
240	1579419
241	1561911
242	1555988
243	1552108
244	1546019
245	1532847
246	1514992
247	1505663
248	1498249
249	1487101
250	1474245
251	1456849
252	1443136
253	1433216
254	1423446
255	1408339
256	1400108
257	1387935
258	1371211
259	1363462
260	1352438
261	1346137
262	1331202
263	1317792
264	1304485
265	1286327
266	1277994
267	1262568
268	1248991
269	1225277
270	1208595
271	1193292
272	1175270
273	1161760
274	1144796
275	1127605
276	1109787
277	1088531
278	1071661
279	1058415
280	1037692
281	1015076
282	993920
283	980391
284	960897
285	944021
286	923817
287	910797
288	893964
289	872804
290	857509
291	840639
292	827042
293	811935
294	794471
295	782797
296	764666
297	752394
298	736100
299	717777
300	702759
301	683586
302	674567
303	656479
304	640872
305	619247
306	604434
307	589256
308	575785
309	558361
310	540745
311	528367
312	513619
313	499542
314	484506
315	470109
316	459890
317	442477
318	430904
319	421055
320	412804
321	400674
322	392677
323	381791
324	369831
325	358746
326	347902
327	337720
328	327419
329	318714
330	308661
331	302305
332	294140
333	287904
334	278236
335	272541
336	268167
337	261678
338	255273
339	247381
340	241090
341	236354
342	230599
343	224637
344	221071
345	215930
346	210405
347	205922
348	203215
349	197654
350	193953
351	193239
352	188840
353	185676
354	182107
355	176841
356	175210
357	172299
358	169366
359	164982
360	162942
361	161556
362	160085
363	159208
364	156986
365	155125
366	153544
367	151896
368	150691
369	150041
370	148701
371	148104
372	146907
373	145833
374	144336
375	143254
376	141161
377	142894
378	141193
379	140799
380	139130
381	138584
382	138035
383	136672
384	135523
385	134529
386	132552
387	132666
388	131089
389	130891
390	129412
391	128478
392	127382
393	127586
394	126498
395	125894
396	125550
397	124931
398	124645
399	123548
400	124251
401	124400
402	122998
403	122604
404	122628
405	122087
406	120602
407	119712
408	119467
409	119125
410	118926
411	117380
412	116529
413	115671
414	114993
415	113094
416	113708
417	113646
418	113241
419	112116
420	111830
421	111599
422	110963
423	111395
424	111359
425	110835
426	110243
427	109322
428	109469
429	110072
430	109332
431	109259
432	108162
433	107763
434	106633
435	105448
436	104691
437	104530
438	103724
439	103473
440	102603
441	101312
442	101717
443	100822
444	100225
445	100303
446	100081
447	99353
448	98374
449	98060
450	98340
451	96940
452	95785
453	95991
454	96086
455	96293
456	95597
457	95076
458	95554
459	94149
460	94179
461	94550
462	92878
463	92870
464	91864
465	90757
466	90360
467	90147
468	89615
469	89027
470	89444
471	88436
472	88223
473	88770
474	88880
475	88221
476	87269
477	86814
478	87256
479	86793
480	86187
481	84491
482	84820
483	85154
484	84749
485	84912
486	83666
487	83738
488	83644
489	83127
490	82774
491	82100
492	81146
493	80675
494	81860
495	80710
496	80359
497	80179
498	80295
499	79676
500	79449
501	79759
502	79293
503	78754
504	79839
505	78515
506	78472
507	78084
508	78722
509	77706
510	76925
511	75837
512	76304
513	76271
514	75403
515	75504
516	75210
517	74890
518	74409
519	74348
520	73254
521	73058
522	73270
523	71349
524	71092
525	71161
526	70112
527	70555
528	70663
529	70195
530	68208
531	68158
532	68376
533	68514
534	68220
535	67645
536	67089
537	66610
538	66769
539	66371
540	66387
541	66009
542	65401
543	65369
544	65782
545	64674
546	64234
547	63419
548	63429
549	63185
550	62442
551	62136
552	62541
553	62027
554	61940
555	61380
556	60957
557	60640
558	61329
559	59768
560	59560
561	59047
562	59247
563	58911
564	58910
565	58824
566	58678
567	58418
568	57741
569	59026
570	57916
571	57101
572	56731
573	55898
574	55452
575	55560
576	55312
577	55358
578	55039
579	54973
580	54239
581	54077
582	54133
583	54351
584	53575
585	53838
586	53914
587	53330
588	52779
589	52653
590	51985
591	52540
592	52663
593	52207
594	52195
595	52216
596	51735
597	51759
598	50748
599	51376
600	51385
601	50470
602	50287
603	50514
604	50356
605	50408
606	49725
607	49391
608	49106
609	49094
610	49181
611	48653
612	48201
613	47769
614	48353
615	48155
616	46988
617	47006
618	47232
619	47153
620	46938
621	46472
622	46544
623	46232
624	45592
625	45215
626	45394
627	45810
628	46115
629	45836
630	44917
631	45134
632	45451
633	45199
634	45328
635	44933
636	45029
637	44407
638	44184
639	43279
640	43135
641	43278
642	43058
643	42522
644	42619
645	42464
646	42112
647	41570
648	41739
649	40986
650	41104
651	41259
652	41315
653	41129
654	40675
655	40700
656	40666
657	40799
658	40570
659	40209
660	40140
661	39959
662	39917
663	39612
664	39181
665	38449
666	38993
667	38905
668	38210
669	37498
670	38411
671	38528
672	37635
673	38001
674	37813
675	37945
676	37465
677	37992
678	37825
679	37242
680	37523
681	36896
682	36831
683	37200
684	37130
685	37318
686	36910
687	37071
688	37392
689	36565
690	36227
691	36518
692	36150
693	35662
694	35770
695	35775
696	35989
697	36027
698	35479
699	34911
700	35519
701	34941
702	34896
703	34531
704	34524
705	34516
706	34426
707	34244
708	34286
709	34382
710	34759
711	34844
712	34685
713	34339
714	33988
715	34746
716	34046
717	34304
718	34295
719	34000
720	33753
721	33547
722	33364
723	33424
724	33399
725	33594
726	33635
727	33723
728	33787
729	32956
730	33621
731	32719
732	32680
733	33299
734	32862
735	32869
736	32863
737	32810
738	32381
739	32187
740	32784
741	32311
742	31798
743	32350
744	31588
745	31469
746	31418
747	31386
748	31413
749	31394
750	32074
751	31367
752	30999
753	31276
754	30898
755	31121
756	30591
757	30705
758	31000
759	30839
760	30721
761	29922
762	30506
763	29915
764	30027
765	29906
766	30042
767	29930
768	28920
769	29268
770	29150
771	29167
772	29071
773	28717
774	28418
775	28727
776	28864
777	28624
778	28665
779	28108
780	28014
781	28415
782	28084
783	28189
784	27899
785	28103
786	28178
787	28050
788	28039
789	28191
790	27884
791	27734
792	27382
793	27706
794	27485
795	26979
796	27149
797	26579
798	26825
799	26773
800	26510
801	26813
802	26550
803	26695
804	26443
805	26246
806	26410
807	26263
808	25592
809	25847
810	25716
811	25640
812	25961
813	25929
814	25762
815	25020
816	25731
817	25545
818	25545
819	25183
820	25663
821	25024
822	24821
823	24785
824	24608
825	24740
826	24812
827	24404
828	24567
829	24578
830	24358
831	24646
832	24373
833	24135
834	23807
835	23339
836	23562
837	23351
838	23679
839	23565
840	23200
841	23370
842	23555
843	23865
844	23447
845	23339
846	23502
847	23677
848	23528
849	23464
850	23274
851	23066
852	23208
853	23636
854	23174
855	23165
856	22947
857	22809
858	22632
859	23053
860	22834
861	22797
862	22869
863	22741
864	22567
865	22355
866	22767
867	22651
868	22546
869	22767
870	22363
871	22274
872	22637
873	22184
874	21832
875	21897
876	21938
877	21867
878	21882
879	21467
880	21389
881	21350
882	21394
883	21303
884	21524
885	21512
886	21640
887	21808
888	21505
889	21359
890	21016
891	21045
892	20753
893	20636
894	20514
895	20587
896	20298
897	20708
898	20590
899	20618
900	20456
901	20541
902	20337
903	20599
904	20621
905	20738
906	20384
907	20869
908	20338
909	20270
910	20083
911	19814
912	19726
913	20078
914	19827
915	20256
916	20325
917	20129
918	20079
919	19791
920	20041
921	20065
922	20154
923	20270
924	19947
925	19959
926	19667
927	19745
928	19731
929	19213
930	19378
931	19113
932	19346
933	19171
934	19759
935	19198
936	19198
937	19396
938	18946
939	19108
940	19138
941	19295
942	18999
943	19379
944	19314
945	18863
946	18794
947	18802
948	19099
949	18840
950	18582
951	18629
952	18427
953	18264
954	18545
955	18551
956	18520
957	18412
958	18585
959	18649
960	18328
961	18310
962	18318
963	18409
964	18031
965	18337
966	18125
967	18076
968	17634
969	17581
970	17638
971	17789
972	17500
973	17940
974	17740
975	17800
976	17591
977	17389
978	17583
979	17304
980	17130
981	17375
982	17055
983	17158
984	17214
985	17253
986	17171
987	17137
988	17043
989	16977
990	17034
991	16623
992	16862
993	16925
994	16899
995	16629
996	16728
997	16660
998	16594
999	16379
1000	110681005