1	6012780816
2	349047429
3	110818321
4	77889190
5	73356518
6	75874314
7	77286227
8	78130389
9	75923388
10	73157433
11	68301539
12	64182815
13	58879497
14	54867454
15	50359978
16	47025363
17	43208116
18	40362563
19	37061836
20	34463036
21	31466902
22	29150504
23	26588725
24	24671904
25	22514776
26	20967558
27	19371580
28	18280436
29	17087029
30	16346977
31	15506876
32	15022654
33	14435870
34	14122745
35	13739575
36	13470980
37	13159465
38	12983590
39	12762519
40	12610226
41	12396873
42	12301496
43	12141569
44	12012540
45	11860332
46	11743477
47	11608810
48	11514968
49	11370928
50	11255843
51	11152780
52	11064723
53	10957235
54	10847557
55	10748372
56	10670507
57	10538103
58	10445684
59	10343802
60	10248820
61	10133228
62	10031552
63	9945705
64	9829707
65	9753104
66	9665560
67	9560660
68	9474977
69	9379853
70	9295211
71	9180040
72	9093028
73	8999705
74	8885264
75	8796856
76	8709017
77	8610530
78	8521143
79	8436375
80	8334449
81	8241988
82	8137732
83	8052613
84	7950640
85	7866272
86	7771449
87	7682232
88	7588519
89	7498570
90	7414851
91	7332640
92	7217251
93	7137150
94	7044170
95	6953114
96	6869464
97	6772707
98	6682190
99	6593766
100	6518241
101	6440018
102	6353798
103	6250008
104	6160582
105	6080706
106	5996918
107	5917618
108	5827619
109	5758335
110	5666674
111	5591844
112	5509434
113	5434066
114	5353177
115	5266271
116	5194021
117	5108275
118	5046396
119	4974684
120	4907039
121	4823171
122	4747405
123	4688717
124	4603789
125	4523755
126	4451600
127	4392052
128	4326571
129	4256475
130	4189240
131	4129134
132	4060121
133	3992046
134	3925719
135	3868061
136	3807141
137	3738358
138	3674585
139	3618319
140	3554935
141	3499810
142	3440109
143	3377434
144	3326595
145	3275217
146	3213356
147	3159805
148	3111136
149	3057076
150	2998571
151	2953014
152	2896231
153	2845829
154	2800588
155	2756094
156	2711679
157	2656505
158	2610461
159	2567602
160	2525624
161	2480657
162	2435289
163	2390252
164	2346684
165	2304500
166	2262189
167	2222722
168	2180499
169	2147648
170	2108870
171	2070801
172	2034493
173	1993462
174	1958402
175	1919800
176	1892796
177	1854410
178	1824123
179	1788536
180	1757072
181	1724683
182	1694763
183	1666014
184	1633031
185	1598045
186	1566541
187	1537344
188	1512340
189	1484478
190	1455009
191	1429444
192	1403024
193	1377586
194	1350707
195	1328646
196	1305020
197	1283067
198	1253963
199	1230808
200	1211291
201	1186367
202	1162779
203	1141714
204	1122552
205	1102475
206	1082972
207	1060860
208	1040709
209	1022069
210	1002734
211	983320
212	967069
213	949599
214	931284
215	911207
216	897526
217	881151
218	864307
219	849970
220	835178
221	820762
222	806096
223	787756
224	774776
225	758778
226	745721
227	729613
228	718705
229	705436
230	692410
231	681445
232	667438
233	652769
234	643425
235	631417
236	621694
237	608696
238	598442
239	587112
240	577602
241	567890
242	556783
243	547311
244	537967
245	528129
246	518787
247	508810
248	501134
249	491341
250	485524
251	476528
252	467661
253	457736
254	447748
255	441393
256	433572
257	425672
258	421001
259	412710
260	404529
261	397711
262	390493
263	384637
264	377068
265	370105
266	365715
267	361264
268	354436
269	347669
270	341886
271	336928
272	330273
273	326160
274	320108
275	316331
276	310042
277	302522
278	299958
279	294412
280	291340
281	285082
282	281316
283	275592
284	271099
285	268728
286	264147
287	260490
288	255975
289	250378
290	247542
291	244699
292	240012
293	235672
294	232281
295	229445
296	226828
297	223425
298	218650
299	215997
300	212432
301	209396
302	205727
303	204061
304	199314
305	196861
306	194639
307	191282
308	189113
309	187120
310	182140
311	179725
312	177537
313	176773
314	173597
315	171971
316	168510
317	165437
318	164043
319	160907
320	158149
321	157173
322	154141
323	152805
324	150949
325	149307
326	146301
327	145298
328	143179
329	140430
330	139136
331	136676
332	135903
333	134329
334	131976
335	131001
336	128941
337	126739
338	126039
339	124003
340	122563
341	120388
342	119253
343	118157
344	116324
345	114234
346	112466
347	111381
348	111158
349	109561
350	107336
351	106298
352	105507
353	104552
354	102762
355	102117
356	100671
357	99044
358	98095
359	97062
360	95432
361	94590
362	93700
363	92717
364	91633
365	89778
366	89426
367	88297
368	87356
369	86787
370	86032
371	84626
372	83694
373	83397
374	82199
375	81382
376	81256
377	79435
378	79229
379	77832
380	77032
381	76229
382	75496
383	75174
384	73620
385	73114
386	72044
387	71663
388	71492
389	70083
390	69660
391	68767
392	68232
393	68110
394	66404
395	66029
396	65606
397	65485
398	63853
399	63830
400	63591
401	62582
402	61418
403	61008
404	60122
405	59383
406	59586
407	59194
408	58393
409	57710
410	57017
411	56709
412	56431
413	55839
414	55370
415	54725
416	54431
417	53849
418	53198
419	52691
420	52422
421	52143
422	51835
423	50682
424	49872
425	50568
426	49394
427	49028
428	48546
429	47868
430	47666
431	47245
432	47094
433	46921
434	46697
435	45874
436	45134
437	45103
438	44695
439	44413
440	43991
441	43811
442	43511
443	43416
444	42786
445	42463
446	42762
447	41682
448	41003
449	40796
450	40724
451	40366
452	40072
453	40137
454	38866
455	39267
456	39014
457	38848
458	38139
459	37911
460	37877
461	37496
462	37379
463	37264
464	36606
465	36938
466	36258
467	36198
468	35892
469	35175
470	35029
471	35045
472	34791
473	34403
474	34214
475	33728
476	33280
477	33103
478	32914
479	33042
480	32795
481	32592
482	32268
483	32085
484	31811
485	31557
486	31269
487	30871
488	30904
489	30595
490	30674
491	30393
492	30270
493	29818
494	29407
495	29618
496	29266
497	29440
498	29153
499	28419
500	28695
501	28228
502	28077
503	28295
504	28023
505	27608
506	27371
507	27300
508	27467
509	27291
510	27070
511	27030
512	26459
513	26321
514	26226
515	26620
516	26084
517	25590
518	26039
519	25735
520	25631
521	25140
522	24988
523	24934
524	24890
525	24789
526	24464
527	24162
528	24099
529	24239
530	24024
531	23897
532	23426
533	23293
534	23163
535	23234
536	23141
537	23213
538	22836
539	22638
540	22567
541	22168
542	22136
543	22200
544	22055
545	22008
546	21998
547	21811
548	21832
549	21687
550	21645
551	21657
552	21158
553	21003
554	21069
555	20650
556	20733
557	20492
558	20448
559	20474
560	20308
561	20365
562	20225
563	19969
564	19752
565	19551
566	19921
567	19580
568	19425
569	19816
570	19431
571	19401
572	19154
573	19172
574	18768
575	19031
576	18579
577	18861
578	18624
579	18282
580	18174
581	18183
582	17896
583	18154
584	18142
585	17749
586	17841
587	17709
588	17693
589	17527
590	17459
591	17119
592	17448
593	17415
594	17251
595	16953
596	16887
597	16963
598	16802
599	16626
600	16749
601	16400
602	16506
603	16412
604	16220
605	16210
606	16057
607	15935
608	16051
609	15843
610	16094
611	15818
612	15625
613	15501
614	15795
615	15587
616	15639
617	15196
618	15398
619	15450
620	15362
621	15287
622	15109
623	15435
624	15045
625	14769
626	14964
627	14905
628	14683
629	14605
630	14707
631	14436
632	14549
633	14428
634	14496
635	14079
636	14091
637	14063
638	14079
639	14197
640	13999
641	13891
642	13805
643	13800
644	13845
645	13831
646	13439
647	13423
648	13393
649	13409
650	13594
651	13267
652	13239
653	13265
654	13074
655	13182
656	13181
657	13005
658	13113
659	13046
660	13005
661	12820
662	12657
663	12331
664	12435
665	12688
666	12520
667	12505
668	12445
669	12509
670	12218
671	12131
672	12253
673	11997
674	12218
675	12072
676	12278
677	12143
678	11792
679	11816
680	12004
681	11764
682	12020
683	11732
684	11755
685	11768
686	11667
687	11704
688	11639
689	11582
690	11409
691	11290
692	11156
693	11561
694	11246
695	11146
696	11222
697	11185
698	11214
699	11106
700	11000
701	10816
702	10887
703	10846
704	10843
705	10718
706	10916
707	10777
708	10623
709	10685
710	10568
711	10702
712	10737
713	10546
714	10468
715	10498
716	10488
717	10206
718	10184
719	10149
720	10213
721	10442
722	10285
723	10185
724	10152
725	10181
726	10186
727	9798
728	10111
729	9905
730	10047
731	10217
732	9823
733	9954
734	9822
735	9915
736	9744
737	9734
738	9616
739	9602
740	9771
741	9434
742	9450
743	9626
744	9611
745	9411
746	9360
747	9598
748	9544
749	9498
750	9412
751	9181
752	9130
753	9231
754	9145
755	8957
756	9103
757	9278
758	9116
759	9068
760	8956
761	9036
762	9073
763	8946
764	8899
765	8718
766	8840
767	8841
768	9044
769	8802
770	8798
771	8619
772	8890
773	8728
774	8666
775	8732
776	8740
777	8608
778	8505
779	8474
780	8362
781	8517
782	8497
783	8573
784	8346
785	8203
786	8311
787	8411
788	8244
789	8515
790	7951
791	8364
792	8277
793	8162
794	8136
795	8191
796	8010
797	8071
798	8042
799	7933
800	8002
801	7979
802	8027
803	7817
804	7846
805	7726
806	7812
807	7685
808	7759
809	7670
810	7686
811	7725
812	7761
813	7729
814	7623
815	7641
816	7429
817	7630
818	7434
819	7300
820	7436
821	7405
822	7514
823	7499
824	7412
825	7354
826	7352
827	7402
828	7329
829	7376
830	7314
831	7191
832	7238
833	7082
834	7253
835	7230
836	7001
837	7136
838	7204
839	7119
840	7082
841	6976
842	7108
843	7027
844	7119
845	6951
846	7054
847	6904
848	6831
849	6800
850	6820
851	6965
852	6804
853	6709
854	6784
855	6787
856	6794
857	6737
858	6616
859	6760
860	6610
861	6749
862	6587
863	6582
864	6683
865	6676
866	6539
867	6734
868	6506
869	6561
870	6435
871	6558
872	6502
873	6729
874	6434
875	6454
876	6536
877	6575
878	6529
879	6469
880	6436
881	6369
882	6450
883	6241
884	6215
885	6279
886	6188
887	6322
888	6336
889	6149
890	6167
891	6255
892	6228
893	6268
894	6256
895	6191
896	6218
897	6352
898	6179
899	5967
900	6040
901	6020
902	5972
903	6028
904	5959
905	5941
906	6087
907	5970
908	5871
909	6044
910	5830
911	5894
912	5763
913	5694
914	5754
915	5841
916	5807
917	5855
918	5856
919	5768
920	5686
921	5790
922	5624
923	5823
924	5684
925	5586
926	5644
927	5567
928	5545
929	5556
930	5666
931	5473
932	5572
933	5563
934	5579
935	5521
936	5564
937	5504
938	5275
939	5387
940	5420
941	5401
942	5351
943	5331
944	5338
945	5420
946	5478
947	5262
948	5350
949	5407
950	5273
951	5296
952	5357
953	5227
954	5256
955	5171
956	5323
957	5347
958	5355
959	5255
960	5270
961	5210
962	5094
963	5117
964	5191
965	5178
966	5117
967	5044
968	4970
969	5024
970	4992
971	4936
972	5077
973	4879
974	5026
975	5059
976	4946
977	4969
978	5056
979	5087
980	4961
981	5041
982	4968
983	4944
984	4901
985	4818
986	4813
987	4767
988	4903
989	4789
990	4825
991	4790
992	4822
993	4848
994	4683
995	4768
996	4721
997	4765
998	4605
999	4645
1000	23842434