1	4486625650
2	882193758
3	347242080
4	158302544
5	73824888
6	40107761
7	23109177
8	15553339
9	11213858
10	8926526
11	7476883
12	6592071
13	6007156
14	5626163
15	5375813
16	5209945
17	5113505
18	5068118
19	5063035
20	5078879
21	5095327
22	5128738
23	5173761
24	5216808
25	5267088
26	5304228
27	5342644
28	5388510
29	5434420
30	5468241
31	5498216
32	5524042
33	5546993
34	5572664
35	5587546
36	5591164
37	5597634
38	5596693
39	5592441
40	5569034
41	5559390
42	5538300
43	5534170
44	5503060
45	5471900
46	5434180
47	5397241
48	5370005
49	5317705
50	5278520
51	5225664
52	5178396
53	5126570
54	5088479
55	5043185
56	4995215
57	4927890
58	4878162
59	4826646
60	4761426
61	4710334
62	4643237
63	4592392
64	4539502
65	4486842
66	4437341
67	4378003
68	4326127
69	4273310
70	4216466
71	4159802
72	4102199
73	4050040
74	4008736
75	3952092
76	3906293
77	3849509
78	3802569
79	3758696
80	3714569
81	3656011
82	3611078
83	3572443
84	3526480
85	3487138
86	3446850
87	3394804
88	3353078
89	3319322
90	3277948
91	3236206
92	3189906
93	3151661
94	3113366
95	3078476
96	3032212
97	2993870
98	2950454
99	2913242
100	2873450
101	2837039
102	2799126
103	2764764
104	2729559
105	2692531
106	2648198
107	2615738
108	2579987
109	2547003
110	2514187
111	2480633
112	2446764
113	2409273
114	2375884
115	2340118
116	2301397
117	2264297
118	2233121
119	2199362
120	2159987
121	2121624
122	2089451
123	2051610
124	2020146
125	1985388
126	1950522
127	1918364
128	1882157
129	1853995
130	1816267
131	1788145
132	1750077
133	1721061
134	1686749
135	1655923
136	1620798
137	1588140
138	1558518
139	1527736
140	1497762
141	1467773
142	1438168
143	1409040
144	1375632
145	1346561
146	1319579
147	1289740
148	1264180
149	1236868
150	1211310
151	1183549
152	1159253
153	1131337
154	1105493
155	1078058
156	1054804
157	1031907
158	1007546
159	979438
160	958127
161	936729
162	911596
163	890456
164	870701
165	850269
166	828552
167	805756
168	788490
169	771001
170	750738
171	731768
172	713063
173	696056
174	679413
175	661814
176	644508
177	628274
178	612245
179	598222
180	583999
181	570731
182	554724
183	542694
184	528872
185	515139
186	500767
187	490720
188	478476
189	466165
190	453963
191	441838
192	432158
193	421457
194	408970
195	400378
196	389878
197	378182
198	369433
199	360822
200	352159
201	344315
202	334094
203	327818
204	319432
205	312126
206	305004
207	297815
208	289311
209	283167
210	276093
211	271292
212	263855
213	257569
214	252566
215	245970
216	240529
217	236400
218	231197
219	225856
220	220324
221	215199
222	209829
223	205520
224	200597
225	197071
226	193364
227	188638
228	184331
229	179927
230	177250
231	173349
232	169361
233	166605
234	162653
235	159973
236	157187
237	153808
238	151042
239	148631
240	145848
241	143664
242	140559
243	138006
244	135537
245	133371
246	131333
247	128821
248	126406
249	124148
250	122244
251	120662
252	119226
253	116778
254	114781
255	113150
256	111747
257	110767
258	108072
259	106537
260	104569
261	103236
262	101366
263	100115
264	99009
265	97751
266	96392
267	95416
268	94094
269	92822
270	91332
271	90070
272	89412
273	87811
274	87042
275	85542
276	85059
277	83769
278	82291
279	81159
280	80168
281	79449
282	78000
283	77241
284	75996
285	75040
286	74735
287	74061
288	73057
289	72793
290	71173
291	71089
292	69902
293	68882
294	68193
295	67151
296	67419
297	66649
298	66079
299	66130
300	64774
301	64522
302	63471
303	63079
304	62566
305	61684
306	61406
307	60703
308	59794
309	58856
310	58706
311	58721
312	58112
313	57639
314	57331
315	56926
316	55924
317	55411
318	55361
319	55138
320	54716
321	53890
322	53737
323	52904
324	52689
325	51953
326	51571
327	51568
328	51114
329	50502
330	49962
331	49918
332	49529
333	49168
334	48627
335	48076
336	48377
337	47568
338	47147
339	46636
340	46532
341	46202
342	45804
343	45935
344	45137
345	45004
346	44770
347	44241
348	43977
349	43451
350	43511
351	43169
352	43078
353	42783
354	42620
355	42371
356	42198
357	41598
358	40936
359	41351
360	40691
361	40740
362	40473
363	40522
364	39766
365	39587
366	39458
367	39193
368	38732
369	38140
370	38128
371	37975
372	37592
373	37674
374	37334
375	37244
376	37229
377	36843
378	37111
379	36815
380	36544
381	35700
382	35888
383	35770
384	35296
385	35249
386	34934
387	35192
388	34957
389	34569
390	34379
391	34240
392	34040
393	33962
394	33491
395	33008
396	33301
397	33083
398	32641
399	32629
400	32063
401	32148
402	32291
403	31959
404	32044
405	31557
406	31580
407	31003
408	31365
409	30706
410	30688
411	30408
412	30344
413	30242
414	30338
415	29709
416	29924
417	29556
418	29536
419	29389
420	29295
421	29057
422	29161
423	28763
424	29085
425	28543
426	28674
427	28700
428	28327
429	28242
430	28037
431	28136
432	27703
433	27717
434	27619
435	27621
436	27202
437	27273
438	27023
439	27048
440	26468
441	26358
442	26315
443	26166
444	26038
445	26039
446	25966
447	25704
448	25348
449	25302
450	25543
451	25582
452	25089
453	25396
454	25297
455	24957
456	24850
457	24749
458	24733
459	24373
460	24482
461	24053
462	24422
463	23925
464	23859
465	23787
466	23533
467	23712
468	23697
469	23418
470	23565
471	23399
472	23421
473	23026
474	22907
475	22866
476	22660
477	22915
478	22677
479	22732
480	22610
481	22263
482	22280
483	22168
484	21929
485	21829
486	21968
487	21913
488	21732
489	21941
490	21780
491	21727
492	21638
493	21517
494	21317
495	21238
496	21218
497	21179
498	20649
499	20883
500	20760
501	20351
502	20370
503	20349
504	20160
505	20241
506	20012
507	19764
508	19736
509	19894
510	19738
511	19613
512	19637
513	19724
514	19314
515	19343
516	19347
517	19515
518	19131
519	19216
520	18957
521	18902
522	19010
523	19033
524	19066
525	19038
526	18649
527	18500
528	18526
529	18528
530	18508
531	18641
532	18277
533	18285
534	18310
535	18069
536	17657
537	17843
538	17898
539	17726
540	17638
541	17445
542	17481
543	17549
544	17538
545	17397
546	17285
547	17285
548	17657
549	17182
550	17390
551	17328
552	17142
553	17137
554	16995
555	17010
556	16829
557	16732
558	16872
559	16801
560	16858
561	16459
562	16625
563	16309
564	16267
565	16273
566	16360
567	16346
568	16320
569	16055
570	15709
571	15992
572	15947
573	15903
574	15767
575	15545
576	15628
577	15797
578	15372
579	15607
580	15447
581	15444
582	15324
583	15311
584	15185
585	15137
586	15001
587	15084
588	14947
589	14707
590	14871
591	14911
592	14948
593	14868
594	14876
595	14764
596	14670
597	14540
598	14376
599	14671
600	14277
601	14344
602	14366
603	14371
604	14117
605	14203
606	14060
607	14186
608	14012
609	14039
610	14078
611	13807
612	13606
613	13782
614	13517
615	13814
616	13523
617	13659
618	13302
619	13553
620	13580
621	13580
622	13221
623	13196
624	13284
625	13333
626	13341
627	13166
628	13076
629	12869
630	13191
631	12886
632	12829
633	12817
634	12869
635	12719
636	12601
637	12661
638	12701
639	12606
640	12531
641	12835
642	12464
643	12513
644	12396
645	12602
646	12274
647	12355
648	12274
649	12559
650	12207
651	12221
652	12259
653	12246
654	12130
655	12106
656	12123
657	11838
658	12050
659	11862
660	11990
661	11646
662	11727
663	11817
664	11653
665	11724
666	11615
667	11741
668	11639
669	11440
670	11525
671	11425
672	11539
673	11367
674	11626
675	11325
676	11271
677	11307
678	11439
679	11085
680	11177
681	11346
682	11318
683	11204
684	11113
685	11188
686	11013
687	11045
688	11013
689	11020
690	10966
691	10884
692	10830
693	10821
694	10760
695	10872
696	10821
697	10782
698	10706
699	10928
700	10463
701	10694
702	10542
703	10368
704	10496
705	10566
706	10621
707	10283
708	10446
709	10336
710	10308
711	10225
712	10308
713	10133
714	10323
715	9860
716	10220
717	10236
718	9930
719	10119
720	9990
721	9947
722	10028
723	10055
724	9802
725	10037
726	9800
727	9923
728	9784
729	9505
730	9771
731	9846
732	9699
733	9492
734	9506
735	9673
736	9433
737	9507
738	9371
739	9533
740	9624
741	9394
742	9451
743	9354
744	9386
745	9252
746	9307
747	9302
748	9081
749	9059
750	9098
751	9268
752	9039
753	9049
754	9104
755	8978
756	8856
757	9011
758	8917
759	9037
760	8919
761	9001
762	8855
763	8776
764	8952
765	8810
766	9019
767	8883
768	8706
769	8790
770	8795
771	8768
772	8639
773	8620
774	8579
775	8508
776	8520
777	8533
778	8528
779	8443
780	8551
781	8425
782	8540
783	8372
784	8405
785	8349
786	8322
787	8307
788	8268
789	8340
790	8207
791	8322
792	8226
793	8229
794	8272
795	8193
796	8160
797	8158
798	8126
799	8087
800	8044
801	8031
802	7950
803	7960
804	7953
805	7954
806	7881
807	7806
808	7928
809	7947
810	7819
811	7747
812	8034
813	7743
814	7687
815	7782
816	7731
817	7732
818	7538
819	7556
820	7785
821	7693
822	7740
823	7515
824	7583
825	7570
826	7542
827	7434
828	7484
829	7603
830	7634
831	7645
832	7385
833	7342
834	7462
835	7325
836	7478
837	7301
838	7264
839	7349
840	7375
841	7300
842	7333
843	7302
844	7285
845	7216
846	7253
847	7174
848	7119
849	7104
850	7189
851	7229
852	7067
853	6973
854	6916
855	7177
856	7118
857	6989
858	6889
859	7016
860	6994
861	6985
862	7032
863	6986
864	7046
865	6881
866	6877
867	6906
868	6768
869	6898
870	6658
871	6771
872	6882
873	6848
874	6840
875	6662
876	6568
877	6732
878	6714
879	6553
880	6645
881	6691
882	6549
883	6510
884	6698
885	6530
886	6486
887	6579
888	6514
889	6562
890	6514
891	6540
892	6599
893	6563
894	6440
895	6596
896	6286
897	6434
898	6449
899	6381
900	6324
901	6203
902	6312
903	6207
904	6434
905	6290
906	6339
907	6257
908	6215
909	6342
910	6239
911	6101
912	6245
913	6137
914	6136
915	6171
916	6043
917	6005
918	6064
919	6061
920	6064
921	6142
922	5927
923	6098
924	6119
925	5974
926	6051
927	6093
928	6112
929	6088
930	5939
931	6042
932	6006
933	5968
934	5871
935	5761
936	6169
937	5970
938	5908
939	5931
940	5862
941	5757
942	5941
943	5686
944	5895
945	5810
946	5753
947	5753
948	5874
949	5787
950	5968
951	5773
952	5698
953	5739
954	5672
955	5737
956	5586
957	5585
958	5579
959	5512
960	5491
961	5463
962	5498
963	5489
964	5456
965	5463
966	5600
967	5520
968	5452
969	5364
970	5555
971	5458
972	5444
973	5428
974	5394
975	5366
976	5442
977	5299
978	5306
979	5349
980	5253
981	5376
982	5376
983	5310
984	5272
985	5214
986	5253
987	5387
988	5304
989	5206
990	5333
991	5083
992	5140
993	5202
994	5309
995	5186
996	5171
997	5187
998	5249
999	5228
1000	23899663