1	6224832577
2	611462274
3	215985245
4	103136338
5	54705083
6	30687251
7	18312377
8	11769145
9	8162793
10	6063665
11	4736217
12	3860043
13	3219472
14	2738491
15	2368305
16	2070672
17	1805994
18	1586464
19	1396152
20	1238796
21	1099152
22	978534
23	875213
24	792430
25	722185
26	663794
27	615597
28	574501
29	538830
30	509479
31	488135
32	468286
33	454307
34	441564
35	430667
36	422250
37	413743
38	404053
39	397149
40	391321
41	386642
42	381092
43	374683
44	368452
45	362838
46	358186
47	352304
48	347884
49	342961
50	337368
51	335373
52	330546
53	327214
54	325999
55	323333
56	325409
57	326761
58	329325
59	332882
60	339138
61	347451
62	358749
63	372466
64	386597
65	404459
66	425428
67	453129
68	483830
69	519556
70	562102
71	610831
72	665150
73	726955
74	797311
75	876111
76	966448
77	1067914
78	1180925
79	1303344
80	1440720
81	1586925
82	1747530
83	1916538
84	2102028
85	2293811
86	2491653
87	2692213
88	2903004
89	3119986
90	3334115
91	3547136
92	3754292
93	3966696
94	4155042
95	4346996
96	4513210
97	4668580
98	4798901
99	4912749
100	5007309
101	5074470
102	5118717
103	5134376
104	5123255
105	5089274
106	5034407
107	4950342
108	4844546
109	4718898
110	4582457
111	4423035
112	4247748
113	4062034
114	3871233
115	3668961
116	3458189
117	3252145
118	3041810
119	2833779
120	2631937
121	2433196
122	2244470
123	2060314
124	1885817
125	1720231
126	1565192
127	1420096
128	1282950
129	1159420
130	1042450
131	937620
132	845998
133	758569
134	682682
135	615210
136	555223
137	501243
138	456720
139	417692
140	382989
141	354328
142	331997
143	310603
144	294676
145	282916
146	273349
147	268160
148	264607
149	264146
150	265077
151	269747
152	276025
153	281648
154	292176
155	302015
156	314966
157	330150
158	346120
159	364939
160	385956
161	407896
162	430319
163	455061
164	484112
165	515263
166	546731
167	583006
168	619199
169	659725
170	703770
171	748327
172	795789
173	846126
174	900447
175	955890
176	1012470
177	1071865
178	1133410
179	1201650
180	1268901
181	1338042
182	1409913
183	1482010
184	1559831
185	1635214
186	1712275
187	1790706
188	1869416
189	1946402
190	2022046
191	2100611
192	2174610
193	2247985
194	2318528
195	2391135
196	2460306
197	2520703
198	2580755
199	2638064
200	2686586
201	2731601
202	2774178
203	2807470
204	2835214
205	2863385
206	2882279
207	2896791
208	2906542
209	2905734
210	2898121
211	2886839
212	2871882
213	2848195
214	2823316
215	2785683
216	2746813
217	2700766
218	2652790
219	2598803
220	2537356
221	2476481
222	2408508
223	2343617
224	2270458
225	2197779
226	2123096
227	2046239
228	1968438
229	1887630
230	1808575
231	1727803
232	1648862
233	1571175
234	1493640
235	1419716
236	1345883
237	1273344
238	1199329
239	1131818
240	1064558
241	1001298
242	938105
243	878950
244	821402
245	768511
246	712741
247	665357
248	620178
249	573593
250	533295
251	493104
252	457337
253	423272
254	390828
255	361721
256	335557
257	309497
258	285945
259	265032
260	245454
261	229024
262	213516
263	199232
264	186240
265	175417
266	165288
267	155916
268	147893
269	140666
270	135011
271	131292
272	126731
273	123698
274	121199
275	119639
276	117971
277	117933
278	117200
279	116840
280	117931
281	118156
282	118874
283	119825
284	121385
285	122594
286	125010
287	127049
288	129488
289	131372
290	134520
291	136844
292	139303
293	141305
294	143448
295	146502
296	148455
297	151551
298	152681
299	155119
300	158040
301	159498
302	161716
303	163830
304	164784
305	165569
306	167079
307	168252
308	169133
309	170461
310	171453
311	171341
312	170578
313	171471
314	170425
315	169114
316	168667
317	168511
318	167109
319	166197
320	164467
321	163067
322	161197
323	159704
324	157952
325	156237
326	153122
327	151239
328	148104
329	146317
330	143525
331	139974
332	137391
333	135257
334	131617
335	129062
336	126933
337	123244
338	120841
339	118819
340	115001
341	111630
342	109203
343	106093
344	103769
345	100641
346	97306
347	95093
348	92259
349	90225
350	87372
351	84948
352	82901
353	80874
354	78915
355	77323
356	75531
357	73270
358	72081
359	71126
360	69541
361	67764
362	66753
363	66553
364	65425
365	64333
366	63316
367	63642
368	63144
369	62842
370	62391
371	62082
372	62410
373	62908
374	62660
375	62945
376	62942
377	63917
378	63494
379	64489
380	64649
381	64984
382	66028
383	66619
384	67195
385	68199
386	68394
387	69016
388	69853
389	71542
390	72124
391	72979
392	73584
393	74448
394	76188
395	77159
396	78110
397	78732
398	79752
399	80405
400	81595
401	82230
402	82536
403	83210
404	84033
405	84440
406	85002
407	86286
408	86963
409	86785
410	87071
411	87819
412	88038
413	88192
414	88558
415	88638
416	88689
417	88736
418	88850
419	88835
420	88880
421	88900
422	88659
423	87586
424	88027
425	87712
426	86479
427	85960
428	85201
429	84629
430	84161
431	83129
432	82075
433	81158
434	80135
435	79674
436	78609
437	77760
438	76628
439	75043
440	74149
441	73388
442	72402
443	70834
444	69779
445	69143
446	68020
447	66341
448	65549
449	64310
450	63112
451	62190
452	60681
453	60115
454	59176
455	58148
456	56725
457	55559
458	54529
459	53418
460	52540
461	51712
462	50237
463	50036
464	48914
465	47802
466	47410
467	46754
468	45694
469	44747
470	43974
471	43482
472	42697
473	42465
474	41904
475	40779
476	40871
477	40234
478	39939
479	39038
480	39310
481	38862
482	38122
483	38100
484	38217
485	37936
486	37559
487	37179
488	37255
489	37462
490	36826
491	36785
492	36886
493	36716
494	36857
495	36684
496	36655
497	36903
498	36163
499	36548
500	36939
501	36961
502	36482
503	36876
504	37037
505	37271
506	37249
507	37327
508	37254
509	37627
510	37570
511	37945
512	37737
513	38073
514	38199
515	37975
516	38235
517	38276
518	38288
519	38104
520	38099
521	38544
522	38127
523	38306
524	37760
525	37727
526	38069
527	37785
528	37432
529	37170
530	37299
531	37314
532	36836
533	36609
534	36300
535	36072
536	36497
537	35718
538	35358
539	35378
540	35183
541	34656
542	34774
543	34346
544	34511
545	33848
546	33380
547	33046
548	32959
549	32901
550	32701
551	32304
552	32063
553	31812
554	31655
555	31457
556	30969
557	30765
558	30339
559	30241
560	29874
561	29895
562	29642
563	29249
564	28696
565	28426
566	28384
567	28362
568	27933
569	27729
570	27470
571	27090
572	27025
573	26687
574	26091
575	26376
576	25943
577	26202
578	26075
579	25581
580	25522
581	25493
582	25291
583	25164
584	24827
585	24740
586	24632
587	24687
588	24329
589	24503
590	24448
591	24795
592	24427
593	24372
594	24497
595	24357
596	24322
597	24285
598	24246
599	24269
600	24401
601	24191
602	24358
603	24314
604	24250
605	24199
606	24452
607	24377
608	24560
609	24443
610	24544
611	24518
612	24227
613	24414
614	24405
615	24562
616	24680
617	24895
618	24212
619	24618
620	24561
621	24667
622	24560
623	24219
624	24551
625	24673
626	24310
627	24446
628	24579
629	24106
630	24171
631	24132
632	23951
633	23942
634	24098
635	24063
636	23854
637	23597
638	23594
639	23521
640	23467
641	23445
642	23211
643	23387
644	22992
645	22998
646	22894
647	23179
648	22680
649	22312
650	22515
651	22037
652	22049
653	22004
654	21971
655	21779
656	21529
657	21366
658	21244
659	21285
660	21044
661	21025
662	20959
663	20905
664	20621
665	20527
666	20369
667	20483
668	20088
669	20084
670	19510
671	19808
672	19465
673	19573
674	19510
675	19222
676	19003
677	18830
678	18764
679	18973
680	19088
681	18505
682	18491
683	18195
684	18311
685	18121
686	17890
687	17739
688	17854
689	17616
690	17677
691	17465
692	17563
693	17244
694	17181
695	17081
696	17315
697	17134
698	16968
699	16952
700	17047
701	16695
702	16764
703	17102
704	16912
705	16605
706	16576
707	16692
708	16421
709	16479
710	16688
711	16350
712	16359
713	16270
714	16299
715	16355
716	16469
717	15953
718	16311
719	16357
720	16080
721	16299
722	16219
723	16221
724	15938
725	16008
726	15881
727	16094
728	16112
729	15718
730	15885
731	15816
732	15688
733	15852
734	16092
735	16090
736	16033
737	15917
738	15648
739	15548
740	15480
741	15910
742	15587
743	15719
744	15563
745	15496
746	15610
747	15529
748	15200
749	14948
750	14992
751	14915
752	14979
753	14818
754	14748
755	14947
756	14784
757	14861
758	14703
759	14709
760	14702
761	14433
762	14506
763	14627
764	14458
765	14248
766	14088
767	14230
768	14296
769	14196
770	14182
771	14123
772	14162
773	13932
774	13919
775	13764
776	13884
777	13821
778	13716
779	13789
780	13817
781	13689
782	13744
783	13757
784	13508
785	13212
786	13530
787	13428
788	13373
789	13233
790	13107
791	12932
792	12964
793	13048
794	13102
795	13074
796	12881
797	12929
798	12768
799	12583
800	12752
801	12739
802	12670
803	12551
804	12535
805	12681
806	12515
807	12310
808	12743
809	12397
810	12255
811	12420
812	12370
813	12459
814	12248
815	12400
816	12251
817	12166
818	12039
819	12075
820	12052
821	12034
822	12011
823	11882
824	11877
825	11902
826	11828
827	11879
828	11952
829	11691
830	11998
831	11715
832	11906
833	11771
834	11726
835	11753
836	11881
837	11865
838	11650
839	11691
840	11694
841	11513
842	11526
843	11503
844	11524
845	11603
846	11337
847	11157
848	11331
849	11338
850	11402
851	11117
852	11214
853	11039
854	11228
855	11091
856	11167
857	10901
858	10934
859	10974
860	10876
861	11229
862	10843
863	10833
864	10862
865	10732
866	11095
867	10784
868	10648
869	10788
870	10754
871	10793
872	10606
873	10727
874	10633
875	10332
876	10413
877	10400
878	10600
879	10467
880	10443
881	10351
882	10373
883	10224
884	10044
885	10086
886	10078
887	9847
888	9731
889	9908
890	9838
891	9955
892	9956
893	9787
894	9904
895	9849
896	9827
897	9641
898	9737
899	9669
900	9710
901	9564
902	9601
903	9657
904	9710
905	9732
906	9726
907	9346
908	9820
909	9505
910	9540
911	9449
912	9287
913	9515
914	9469
915	9261
916	9201
917	9010
918	9345
919	9402
920	9292
921	9037
922	9176
923	9051
924	9174
925	9175
926	9086
927	9135
928	9103
929	9172
930	9037
931	8868
932	9117
933	9014
934	8973
935	8863
936	8840
937	8922
938	8548
939	8862
940	8754
941	8655
942	8599
943	8651
944	8520
945	8647
946	8544
947	8480
948	8504
949	8455
950	8418
951	8329
952	8291
953	8349
954	8284
955	8539
956	8292
957	8248
958	8354
959	8196
960	8334
961	8212
962	8139
963	8334
964	8251
965	8248
966	8046
967	8056
968	8063
969	7931
970	7975
971	8004
972	7953
973	8104
974	8002
975	8086
976	7917
977	7923
978	7898
979	8072
980	7932
981	7861
982	7752
983	7903
984	8000
985	7857
986	7740
987	7749
988	7806
989	7838
990	7610
991	7853
992	7711
993	7700
994	7579
995	7505
996	7545
997	7473
998	7302
999	7341
1000	24687251