1	5379736488
2	865562453
3	337718620
4	170919950
5	87017768
6	55129162
7	34324467
8	24779450
9	17607229
10	13507088
11	10297785
12	8215896
13	6544525
14	5361017
15	4441208
16	3769391
17	3250304
18	2864524
19	2564163
20	2354535
21	2204320
22	2096724
23	2044430
24	2020117
25	2021539
26	2056737
27	2110918
28	2186282
29	2273469
30	2367430
31	2483824
32	2600898
33	2724153
34	2844450
35	2967102
36	3092421
37	3211733
38	3334273
39	3441337
40	3559479
41	3662525
42	3752652
43	3841854
44	3925103
45	3996395
46	4057759
47	4117311
48	4163014
49	4199198
50	4233037
51	4253359
52	4260280
53	4269005
54	4266480
55	4252386
56	4246116
57	4230697
58	4206223
59	4176483
60	4139561
61	4100997
62	4065348
63	4022912
64	3980629
65	3926755
66	3881846
67	3831021
68	3777052
69	3721799
70	3668171
71	3612874
72	3560187
73	3511543
74	3455704
75	3402806
76	3347380
77	3299539
78	3251233
79	3204776
80	3155803
81	3105894
82	3068843
83	3025952
84	2981853
85	2943309
86	2905930
87	2868235
88	2829461
89	2793197
90	2756213
91	2723379
92	2689549
93	2659283
94	2632194
95	2604484
96	2575956
97	2545634
98	2516025
99	2487580
100	2466605
101	2441367
102	2416797
103	2388433
104	2365777
105	2343609
106	2317676
107	2295012
108	2265636
109	2243082
110	2222103
111	2190822
112	2168563
113	2147276
114	2120577
115	2098621
116	2072861
117	2050757
118	2024739
119	2001288
120	1972191
121	1946021
122	1919440
123	1891673
124	1864985
125	1837452
126	1811204
127	1784586
128	1756031
129	1730062
130	1703513
131	1675047
132	1647128
133	1621320
134	1593599
135	1568234
136	1540162
137	1516019
138	1488723
139	1460028
140	1434997
141	1403877
142	1379605
143	1355125
144	1328140
145	1303834
146	1279175
147	1250349
148	1223147
149	1198892
150	1177624
151	1152144
152	1128563
153	1103619
154	1079716
155	1056668
156	1034260
157	1011741
158	990438
159	969023
160	944591
161	925426
162	904533
163	886839
164	866547
165	845618
166	827618
167	808573
168	789242
169	772499
170	755404
171	736520
172	719557
173	705815
174	687854
175	670547
176	655592
177	639847
178	627299
179	613224
180	599793
181	585878
182	572107
183	558998
184	547383
185	534404
186	524004
187	511047
188	499832
189	487917
190	476182
191	465323
192	453674
193	444803
194	432496
195	423130
196	413164
197	405035
198	395575
199	386338
200	378258
201	369730
202	362009
203	354016
204	346545
205	338792
206	331419
207	324219
208	316966
209	309855
210	303026
211	295789
212	290307
213	284215
214	278735
215	272812
216	266702
217	262500
218	257700
219	251039
220	246961
221	240972
222	236657
223	232745
224	227258
225	222347
226	217754
227	214230
228	209541
229	205277
230	201587
231	198179
232	194210
233	189672
234	186277
235	183240
236	180487
237	176749
238	174616
239	170717
240	168152
241	165620
242	162950
243	159843
244	155944
245	154462
246	151780
247	149360
248	147236
249	144490
250	142459
251	140247
252	137101
253	134778
254	132576
255	130652
256	128688
257	126018
258	124686
259	122695
260	121435
261	119173
262	117101
263	115220
264	113065
265	112157
266	110559
267	108848
268	107457
269	106286
270	104359
271	103501
272	101937
273	100316
274	99815
275	98542
276	96507
277	95494
278	94821
279	93782
280	92250
281	91468
282	89725
283	88609
284	87930
285	86037
286	85116
287	84815
288	83251
289	82417
290	82047
291	81138
292	80453
293	79301
294	78861
295	77418
296	76512
297	75485
298	74580
299	74432
300	73597
301	72562
302	72066
303	71125
304	70585
305	69853
306	69164
307	68435
308	67743
309	66954
310	66094
311	65775
312	64821
313	64625
314	63733
315	63410
316	62634
317	62071
318	61523
319	61774
320	61316
321	60763
322	59468
323	59203
324	58365
325	58314
326	57177
327	57172
328	56159
329	56196
330	55804
331	55400
332	54679
333	54497
334	53645
335	53563
336	53020
337	52371
338	52506
339	51890
340	51365
341	50546
342	50637
343	50487
344	49857
345	49581
346	49431
347	49251
348	48503
349	48396
350	47675
351	47556
352	47078
353	46781
354	46263
355	46123
356	45530
357	45461
358	44667
359	44334
360	44121
361	43626
362	43522
363	43102
364	42405
365	41987
366	42024
367	41718
368	41722
369	41204
370	41454
371	40881
372	40384
373	40272
374	40207
375	39258
376	39245
377	39091
378	38798
379	38706
380	38045
381	38179
382	37795
383	37479
384	37468
385	37180
386	36556
387	36607
388	36523
389	35893
390	35991
391	35855
392	35214
393	35337
394	34862
395	34897
396	34555
397	33936
398	34150
399	34057
400	33793
401	33535
402	33537
403	33282
404	33138
405	33094
406	32769
407	32540
408	32012
409	32682
410	31647
411	32043
412	31808
413	31550
414	31004
415	30749
416	30499
417	30597
418	30566
419	30115
420	29936
421	29655
422	29516
423	29818
424	29286
425	29414
426	29179
427	28867
428	28805
429	28682
430	28320
431	28361
432	28200
433	27818
434	27868
435	27449
436	27678
437	27365
438	26819
439	26965
440	26766
441	26651
442	26357
443	26038
444	26249
445	26174
446	26244
447	25797
448	25578
449	25353
450	25300
451	25177
452	24818
453	24912
454	24930
455	24719
456	24750
457	24663
458	24377
459	24393
460	24036
461	24094
462	23606
463	23865
464	23448
465	23604
466	23150
467	23231
468	23169
469	22831
470	22823
471	22606
472	22276
473	22496
474	22292
475	22255
476	21964
477	21962
478	21813
479	21760
480	21640
481	21501
482	21401
483	21351
484	21392
485	21260
486	21285
487	21006
488	21188
489	21012
490	20570
491	20479
492	20904
493	20550
494	20431
495	20254
496	20107
497	19964
498	19660
499	19782
500	19568
501	19438
502	19505
503	19697
504	19268
505	19454
506	19070
507	19235
508	19155
509	19046
510	19048
511	18812
512	18696
513	18664
514	18330
515	18257
516	18213
517	18248
518	17917
519	18086
520	18231
521	17938
522	17797
523	17804
524	17566
525	17724
526	17322
527	17411
528	17433
529	17697
530	17190
531	17063
532	17023
533	16704
534	16837
535	17150
536	16774
537	16551
538	16628
539	16510
540	16361
541	16285
542	16236
543	16127
544	16286
545	16058
546	16013
547	16035
548	15905
549	15949
550	15694
551	15635
552	15593
553	15527
554	15496
555	15723
556	15367
557	15255
558	15293
559	15253
560	15153
561	15054
562	15009
563	15024
564	14967
565	14778
566	14860
567	14485
568	14640
569	14505
570	14468
571	14460
572	14227
573	14132
574	14212
575	14063
576	14089
577	14076
578	14107
579	13715
580	13991
581	13833
582	13837
583	13903
584	13719
585	13629
586	13451
587	13593
588	13335
589	13620
590	13424
591	13493
592	13364
593	13388
594	13096
595	13279
596	13075
597	13114
598	12810
599	12863
600	12759
601	12829
602	12721
603	12881
604	12822
605	12572
606	12641
607	12700
608	12491
609	12433
610	12493
611	12343
612	12233
613	12291
614	12199
615	12082
616	12111
617	11921
618	12218
619	12301
620	12041
621	11870
622	12030
623	11777
624	11615
625	11735
626	11671
627	11379
628	11578
629	11573
630	11369
631	11425
632	11405
633	11556
634	11426
635	11209
636	11281
637	11056
638	11182
639	10996
640	11204
641	11156
642	11052
643	11149
644	10809
645	10845
646	10840
647	10958
648	10907
649	10746
650	10910
651	10506
652	10616
653	10671
654	10544
655	10576
656	10422
657	10609
658	10536
659	10562
660	10382
661	10471
662	10412
663	10413
664	10266
665	10193
666	10189
667	10186
668	10214
669	10180
670	10115
671	10059
672	10144
673	9947
674	9836
675	9787
676	9754
677	9834
678	9502
679	9610
680	9726
681	9648
682	9685
683	9648
684	9587
685	9417
686	9594
687	9411
688	9570
689	9409
690	9242
691	9338
692	9461
693	9495
694	9374
695	9413
696	9307
697	9182
698	9239
699	9149
700	9168
701	9049
702	9152
703	8920
704	9113
705	8820
706	8910
707	8864
708	8860
709	8912
710	8913
711	8696
712	8855
713	8817
714	8652
715	8628
716	8717
717	8604
718	8514
719	8549
720	8333
721	8688
722	8300
723	8497
724	8326
725	8393
726	8371
727	8249
728	8168
729	8322
730	8268
731	8108
732	8289
733	8104
734	8209
735	8043
736	8021
737	8071
738	8022
739	8133
740	8021
741	7944
742	7919
743	7679
744	8093
745	7949
746	7917
747	7855
748	7914
749	7822
750	7873
751	7715
752	7775
753	7705
754	7720
755	7778
756	7531
757	7635
758	7640
759	7570
760	7606
761	7643
762	7499
763	7652
764	7653
765	7567
766	7512
767	7419
768	7310
769	7397
770	7222
771	7231
772	7247
773	7222
774	7343
775	7238
776	7039
777	7179
778	7141
779	7279
780	7155
781	7017
782	7109
783	6955
784	7017
785	7075
786	6945
787	6919
788	7004
789	6943
790	6828
791	6799
792	6807
793	6828
794	6735
795	6667
796	6821
797	6742
798	6767
799	6746
800	6628
801	6678
802	6721
803	6731
804	6498
805	6710
806	6373
807	6357
808	6338
809	6219
810	6430
811	6318
812	6397
813	6288
814	6325
815	6356
816	6307
817	6215
818	6358
819	6026
820	6206
821	6142
822	6153
823	6158
824	5933
825	6233
826	6117
827	6026
828	6156
829	6036
830	5985
831	6084
832	5957
833	5990
834	6148
835	5940
836	5767
837	6119
838	5921
839	5856
840	5925
841	5902
842	5809
843	5808
844	5853
845	5838
846	5844
847	5834
848	5853
849	5739
850	5860
851	5743
852	5585
853	5635
854	5578
855	5639
856	5593
857	5569
858	5611
859	5552
860	5535
861	5526
862	5599
863	5490
864	5309
865	5445
866	5361
867	5585
868	5425
869	5355
870	5384
871	5375
872	5419
873	5262
874	5281
875	5262
876	5369
877	5247
878	5289
879	5269
880	5321
881	5305
882	5257
883	5332
884	5227
885	5248
886	5156
887	5149
888	5132
889	5136
890	5091
891	5058
892	5108
893	5157
894	4927
895	5042
896	5059
897	4996
898	5162
899	5076
900	5139
901	5076
902	5154
903	5032
904	4976
905	4999
906	4859
907	4860
908	4897
909	4840
910	4946
911	4853
912	4881
913	4779
914	4920
915	4922
916	4690
917	4811
918	4603
919	4690
920	4792
921	4738
922	4566
923	4614
924	4620
925	4779
926	4566
927	4621
928	4498
929	4553
930	4617
931	4532
932	4568
933	4615
934	4366
935	4565
936	4495
937	4594
938	4534
939	4392
940	4512
941	4483
942	4504
943	4534
944	4455
945	4475
946	4413
947	4386
948	4496
949	4240
950	4403
951	4350
952	4459
953	4224
954	4400
955	4369
956	4384
957	4259
958	4246
959	4347
960	4279
961	4241
962	4318
963	4218
964	4236
965	4259
966	4353
967	4359
968	4183
969	4134
970	4128
971	4195
972	4217
973	4156
974	4011
975	4170
976	4124
977	4109
978	4179
979	4067
980	4044
981	4116
982	4073
983	4076
984	4126
985	3988
986	4165
987	4078
988	3945
989	3931
990	3987
991	3946
992	3940
993	3935
994	3998
995	3846
996	3861
997	3907
998	3947
999	3945
1000	13349440