1	4854708682
2	641736887
3	210363514
4	97277708
5	54685790
6	35365162
7	25376798
8	19630715
9	16051626
10	13404227
11	11094899
12	9267000
13	7722259
14	6518670
15	5653392
16	5092299
17	4796384
18	4748377
19	4818510
20	5052006
21	5455569
22	5936713
23	6520204
24	7151391
25	7856846
26	8558944
27	9217051
28	9814292
29	10216435
30	10529512
31	10681945
32	10628908
33	10502333
34	10327590
35	10088105
36	9876627
37	9679997
38	9584269
39	9591062
40	9709110
41	10034134
42	10479757
43	11123552
44	11971848
45	13036502
46	14330484
47	15770130
48	17409895
49	19204929
50	21157755
51	23174212
52	25245279
53	27397520
54	29503195
55	31512595
56	33422383
57	35185947
58	36682708
59	37894437
60	38718090
61	39162272
62	39281564
63	38978660
64	38329019
65	37253972
66	35928668
67	34287834
68	32424557
69	30322367
70	28026768
71	25716852
72	23319351
73	20926680
74	18616994
75	16435243
76	14373292
77	12474936
78	10756851
79	9227732
80	7846231
81	6659476
82	5648966
83	4794251
84	4068110
85	3470246
86	2981326
87	2596753
88	2290437
89	2049161
90	1864856
91	1731173
92	1649988
93	1579899
94	1548087
95	1524391
96	1510629
97	1507247
98	1520824
99	1541091
100	1559347
101	1586958
102	1618884
103	1648671
104	1682459
105	1720415
106	1762979
107	1812050
108	1855906
109	1906861
110	1957744
111	2013029
112	2071752
113	2125950
114	2170129
115	2226975
116	2266414
117	2308356
118	2354979
119	2393015
120	2418021
121	2434149
122	2445562
123	2450499
124	2453849
125	2445484
126	2429624
127	2394957
128	2367192
129	2332833
130	2271651
131	2220955
132	2155435
133	2095149
134	2023379
135	1945579
136	1867813
137	1789371
138	1707793
139	1623641
140	1537365
141	1460508
142	1384328
143	1313594
144	1242866
145	1177330
146	1116065
147	1053683
148	1001379
149	955345
150	911851
151	872648
152	831962
153	802308
154	776785
155	754390
156	732273
157	713279
158	701330
159	690093
160	680452
161	672328
162	670771
163	668290
164	668587
165	667876
166	668798
167	673891
168	675272
169	681647
170	688309
171	692441
172	699699
173	706471
174	712087
175	715600
176	720178
177	726186
178	733280
179	736285
180	740769
181	743548
182	745307
183	747788
184	750132
185	746375
186	743638
187	740900
188	734998
189	729901
190	722468
191	718116
192	712239
193	701195
194	689301
195	679077
196	671044
197	660578
198	647074
199	633884
200	621150
201	607290
202	592344
203	579723
204	564702
205	550691
206	538515
207	523517
208	512369
209	500997
210	488898
211	477217
212	461186
213	453789
214	444815
215	433641
216	425341
217	416845
218	410783
219	402415
220	396949
221	389624
222	386728
223	381581
224	377637
225	374193
226	370716
227	368955
228	367927
229	365049
230	366245
231	368225
232	365717
233	364307
234	365271
235	364150
236	365851
237	365718
238	365589
239	365103
240	364049
241	363418
242	361979
243	364291
244	363077
245	363109
246	362113
247	362128
248	359980
249	359270
250	355840
251	355208
252	352236
253	350600
254	347583
255	347084
256	345175
257	340523
258	337126
259	333534
260	329973
261	327123
262	324426
263	318849
264	315375
265	310840
266	307050
267	302988
268	298707
269	296901
270	293329
271	288562
272	283036
273	278832
274	275027
275	272196
276	268515
277	264879
278	262127
279	258854
280	257166
281	252902
282	249821
283	246682
284	246052
285	244173
286	241094
287	238471
288	236217
289	234538
290	235283
291	232933
292	232314
293	230274
294	230021
295	229216
296	230337
297	227981
298	227218
299	226392
300	224131
301	225035
302	222380
303	223439
304	221367
305	221634
306	220858
307	219548
308	219652
309	218625
310	217892
311	216256
312	215791
313	215162
314	214605
315	213012
316	212112
317	210061
318	209724
319	209025
320	207669
321	205771
322	204403
323	204873
324	201894
325	200355
326	198881
327	197558
328	196743
329	195158
330	193365
331	192943
332	191846
333	189181
334	186826
335	184886
336	184864
337	182011
338	180787
339	179762
340	177167
341	176599
342	176617
343	174210
344	172713
345	172896
346	170873
347	168810
348	167583
349	165528
350	166500
351	164402
352	163278
353	162687
354	161670
355	161113
356	160071
357	158964
358	158351
359	157473
360	156860
361	155691
362	154557
363	154239
364	154201
365	154522
366	153250
367	151947
368	152267
369	151179
370	151221
371	150543
372	149654
373	148432
374	148630
375	146399
376	146413
377	145781
378	145387
379	144547
380	143476
381	142530
382	143229
383	141330
384	140894
385	139710
386	138061
387	137173
388	137616
389	136243
390	134586
391	135112
392	133934
393	134535
394	133119
395	132092
396	130979
397	130424
398	130334
399	128900
400	128306
401	126841
402	127099
403	125675
404	124882
405	123804
406	123974
407	123096
408	122669
409	121399
410	120623
411	119539
412	119299
413	118374
414	118322
415	117167
416	117456
417	116751
418	116038
419	115799
420	114069
421	113951
422	113870
423	112969
424	112721
425	112284
426	112323
427	112470
428	112124
429	111418
430	110436
431	109431
432	109341
433	108264
434	108405
435	108763
436	108053
437	107269
438	106563
439	105735
440	105578
441	104994
442	104264
443	102861
444	102032
445	102568
446	101961
447	101487
448	101296
449	100695
450	100390
451	99804
452	99325
453	99991
454	99279
455	98953
456	97845
457	98279
458	97745
459	97783
460	96525
461	96133
462	95945
463	95362
464	95048
465	94990
466	93984
467	94095
468	93421
469	93812
470	93057
471	92358
472	92219
473	91247
474	90873
475	90793
476	89979
477	89696
478	89749
479	88466
480	89112
481	88859
482	87742
483	88410
484	87412
485	86961
486	86736
487	86545
488	85670
489	85241
490	84887
491	84270
492	83980
493	84125
494	83754
495	83713
496	83594
497	82894
498	81746
499	81729
500	82337
501	81899
502	81705
503	80993
504	80609
505	80226
506	79467
507	79697
508	79182
509	79278
510	78133
511	78611
512	78364
513	77193
514	77335
515	77438
516	76839
517	76616
518	77032
519	76996
520	76080
521	76568
522	75677
523	75299
524	74736
525	74430
526	74840
527	74459
528	74250
529	74111
530	73177
531	72805
532	72017
533	72118
534	71392
535	71735
536	71461
537	71130
538	70857
539	70637
540	70106
541	70217
542	70310
543	70198
544	68728
545	69455
546	68558
547	68290
548	68522
549	68094
550	68133
551	67328
552	67190
553	67330
554	66449
555	67063
556	66907
557	66828
558	66474
559	65435
560	65465
561	65010
562	65132
563	64794
564	64243
565	64339
566	64263
567	64616
568	63479
569	63491
570	62836
571	62448
572	62750
573	62832
574	62687
575	62846
576	62431
577	62214
578	61956
579	62725
580	62383
581	61637
582	61087
583	61178
584	60214
585	60993
586	60125
587	60081
588	59871
589	59644
590	60140
591	59861
592	59385
593	58785
594	58987
595	58714
596	58107
597	57974
598	57793
599	57802
600	56895
601	56469
602	56964
603	56657
604	55489
605	55730
606	55788
607	55389
608	55864
609	55337
610	55702
611	55043
612	55019
613	54698
614	54334
615	54223
616	54440
617	54010
618	53954
619	53274
620	52819
621	52619
622	52638
623	52554
624	52156
625	52462
626	52562
627	51813
628	51653
629	51464
630	51269
631	51093
632	50743
633	50557
634	49974
635	50272
636	50231
637	49463
638	50304
639	49522
640	49479
641	49421
642	49188
643	49262
644	48628
645	48490
646	49584
647	48491
648	48543
649	48751
650	48181
651	48277
652	47831
653	48316
654	47925
655	47879
656	47627
657	47211
658	47023
659	46807
660	46985
661	46595
662	46959
663	46873
664	45972
665	46421
666	45870
667	45952
668	46453
669	45743
670	45815
671	45576
672	44957
673	44765
674	44961
675	44711
676	44113
677	44245
678	44515
679	43812
680	43707
681	43506
682	43537
683	43556
684	43119
685	43452
686	43418
687	43154
688	42603
689	42763
690	42836
691	42569
692	42242
693	41803
694	41983
695	42025
696	42095
697	42010
698	42007
699	41522
700	41313
701	41276
702	41165
703	41058
704	40670
705	41140
706	40463
707	40568
708	40166
709	40151
710	40251
711	40095
712	39986
713	39544
714	39894
715	39477
716	39932
717	39254
718	39190
719	38993
720	38810
721	38621
722	38450
723	38202
724	38465
725	38626
726	38686
727	38350
728	38101
729	38300
730	38290
731	37589
732	37189
733	37454
734	36764
735	36983
736	37184
737	36595
738	36687
739	36750
740	36598
741	36697
742	36843
743	36010
744	36498
745	36471
746	36136
747	36481
748	36457
749	36247
750	36516
751	36029
752	35553
753	35420
754	35607
755	35439
756	34931
757	35359
758	35041
759	34969
760	34747
761	35190
762	34838
763	34361
764	34666
765	34859
766	34836
767	34481
768	34159
769	34100
770	33704
771	34274
772	34118
773	33860
774	33413
775	33256
776	33221
777	33411
778	33062
779	33026
780	32883
781	32851
782	32814
783	32860
784	32926
785	32542
786	32706
787	32525
788	32679
789	32055
790	32252
791	32016
792	32026
793	31943
794	31852
795	31616
796	32059
797	31669
798	31339
799	31267
800	31487
801	31702
802	31221
803	30889
804	30980
805	30653
806	30595
807	30221
808	30379
809	30485
810	30775
811	30786
812	30297
813	30041
814	30215
815	30341
816	30418
817	30358
818	30256
819	30021
820	29760
821	29654
822	29627
823	29926
824	29676
825	30004
826	29273
827	29330
828	29486
829	29021
830	29110
831	28984
832	28726
833	28948
834	28773
835	28820
836	28529
837	28368
838	28444
839	28113
840	28639
841	28411
842	28512
843	28156
844	28235
845	28088
846	28281
847	28221
848	28065
849	27729
850	27796
851	27716
852	27668
853	27571
854	27152
855	27620
856	27838
857	27568
858	27209
859	27262
860	27274
861	26938
862	27072
863	27341
864	26983
865	26660
866	26660
867	26567
868	26773
869	26839
870	27114
871	26225
872	26630
873	26513
874	26663
875	26225
876	25991
877	26356
878	26343
879	26272
880	26187
881	25648
882	25922
883	25668
884	25849
885	25873
886	25532
887	25855
888	25722
889	25543
890	25557
891	25451
892	25231
893	24938
894	25043
895	24850
896	25058
897	25043
898	25033
899	24673
900	24863
901	24915
902	24509
903	24537
904	24661
905	24435
906	24265
907	24537
908	24342
909	24246
910	24316
911	24432
912	24434
913	23849
914	24112
915	24262
916	24108
917	23854
918	23841
919	24197
920	23791
921	23566
922	23829
923	23678
924	23714
925	23529
926	23686
927	23135
928	23461
929	23454
930	22896
931	23291
932	23333
933	22912
934	22966
935	22977
936	22850
937	23028
938	22954
939	23051
940	22852
941	23256
942	23282
943	22816
944	22641
945	22708
946	22648
947	22509
948	22371
949	22549
950	22080
951	22271
952	22330
953	22161
954	22051
955	21920
956	21559
957	21599
958	21502
959	21546
960	21633
961	21536
962	21682
963	21781
964	21540
965	21822
966	21717
967	21881
968	21436
969	21358
970	21313
971	20959
972	21149
973	21387
974	21408
975	21093
976	21441
977	21330
978	21145
979	21048
980	20942
981	21216
982	20702
983	20582
984	20493
985	21035
986	21204
987	20968
988	20693
989	20592
990	20566
991	20919
992	20534
993	20274
994	20185
995	19943
996	20332
997	20428
998	20277
999	20232
1000	162672074