1	6411811364
2	967146884
3	243988184
4	102905607
5	50834985
6	35393550
7	25498249
8	20770814
9	17403217
10	15362917
11	13936351
12	12970853
13	12279059
14	11824056
15	11533973
16	11316206
17	11176679
18	11079763
19	11006281
20	10982622
21	10925356
22	10883796
23	10838622
24	10794437
25	10755702
26	10683260
27	10602141
28	10558746
29	10485304
30	10398477
31	10333340
32	10251132
33	10173190
34	10104297
35	10021614
36	9946308
37	9854616
38	9778519
39	9705606
40	9625310
41	9545708
42	9465615
43	9379809
44	9302069
45	9196125
46	9102481
47	9021682
48	8932786
49	8827911
50	8734175
51	8636708
52	8545633
53	8445951
54	8335180
55	8236110
56	8135494
57	8016145
58	7910856
59	7809417
60	7695708
61	7589455
62	7474127
63	7363461
64	7254244
65	7142861
66	7035191
67	6925299
68	6816217
69	6705093
70	6588233
71	6466893
72	6357706
73	6249401
74	6141866
75	6023164
76	5917412
77	5804110
78	5687575
79	5576072
80	5472784
81	5355399
82	5240783
83	5135268
84	5026405
85	4912374
86	4811939
87	4707040
88	4603191
89	4508563
90	4400663
91	4307313
92	4210289
93	4103514
94	4011453
95	3924962
96	3833768
97	3742309
98	3656688
99	3570817
100	3483237
101	3412679
102	3334442
103	3254473
104	3178366
105	3107875
106	3040497
107	2977590
108	2910601
109	2849243
110	2790590
111	2727773
112	2670111
113	2615675
114	2561719
115	2512411
116	2462296
117	2412910
118	2368606
119	2325739
120	2284564
121	2241224
122	2202880
123	2161115
124	2125714
125	2082850
126	2046543
127	2013815
128	1983313
129	1948578
130	1917239
131	1885019
132	1856966
133	1826653
134	1801712
135	1774844
136	1749152
137	1722177
138	1695626
139	1671614
140	1649604
141	1622692
142	1598565
143	1574769
144	1552070
145	1531906
146	1512306
147	1489510
148	1469792
149	1446473
150	1425644
151	1407283
152	1387241
153	1366838
154	1345811
155	1325544
156	1305811
157	1285978
158	1266168
159	1249872
160	1230115
161	1210932
162	1191148
163	1173350
164	1154157
165	1138278
166	1119255
167	1102055
168	1086051
169	1067805
170	1051249
171	1032080
172	1014017
173	998101
174	980285
175	966048
176	947104
177	928364
178	913112
179	896700
180	882036
181	864954
182	849207
183	831867
184	816519
185	801720
186	785614
187	771431
188	758741
189	745916
190	729610
191	716963
192	702735
193	688716
194	673780
195	661075
196	646494
197	633419
198	620032
199	605326
200	590857
201	580470
202	566866
203	554652
204	542039
205	530685
206	520217
207	506925
208	495326
209	484315
210	473454
211	464019
212	452936
213	442727
214	434478
215	422898
216	412472
217	403737
218	394486
219	384591
220	376350
221	367627
222	359756
223	351259
224	343710
225	335410
226	328554
227	321449
228	313189
229	306398
230	299390
231	292182
232	285498
233	279806
234	272466
235	267201
236	260769
237	255786
238	249387
239	243510
240	238079
241	233454
242	228344
243	221982
244	217586
245	212776
246	208380
247	204474
248	199582
249	196521
250	192249
251	187598
252	181937
253	179708
254	174997
255	171063
256	168206
257	164475
258	160884
259	158757
260	155423
261	152389
262	149209
263	147037
264	143458
265	140375
266	137926
267	136240
268	133497
269	131512
270	129245
271	126207
272	124467
273	122424
274	119821
275	118374
276	116480
277	114477
278	113043
279	110564
280	108707
281	106407
282	105218
283	103470
284	101704
285	100845
286	98951
287	97946
288	96667
289	95165
290	94386
291	92724
292	91994
293	90122
294	89473
295	88248
296	87668
297	87384
298	85811
299	83641
300	83371
301	82259
302	81193
303	80517
304	79230
305	78877
306	78041
307	77329
308	76097
309	75131
310	74505
311	73723
312	73357
313	71903
314	71848
315	71585
316	70286
317	69149
318	69238
319	67914
320	68159
321	66813
322	66137
323	66260
324	66014
325	64960
326	64188
327	63655
328	63550
329	63003
330	62049
331	61696
332	61383
333	60641
334	60909
335	59965
336	59324
337	58671
338	58500
339	58140
340	57514
341	57287
342	56896
343	56243
344	56178
345	55836
346	55180
347	54904
348	54125
349	54430
350	53798
351	53436
352	52761
353	52305
354	52088
355	51984
356	51639
357	51205
358	50916
359	50444
360	50104
361	49757
362	49054
363	49030
364	48617
365	48505
366	48256
367	47798
368	47528
369	47140
370	46967
371	46652
372	46249
373	46095
374	45777
375	45953
376	45581
377	44946
378	44707
379	44733
380	44884
381	44291
382	44407
383	43089
384	43331
385	43185
386	42748
387	42359
388	41897
389	42071
390	41485
391	41586
392	40956
393	41087
394	40711
395	40675
396	40253
397	39948
398	40073
399	39527
400	39572
401	39083
402	39102
403	38283
404	38710
405	38130
406	38269
407	37489
408	37383
409	37332
410	37166
411	36828
412	36688
413	36305
414	36015
415	35878
416	35563
417	35454
418	35237
419	35007
420	35278
421	34795
422	35010
423	34645
424	34728
425	34129
426	33976
427	33813
428	33827
429	33172
430	33103
431	33447
432	33210
433	33139
434	32864
435	32369
436	32571
437	32083
438	31906
439	31647
440	31746
441	31226
442	31383
443	31453
444	31394
445	31077
446	30988
447	30872
448	30360
449	30383
450	30167
451	29899
452	29966
453	29778
454	29434
455	28973
456	28979
457	28838
458	28899
459	28690
460	28503
461	28404
462	28522
463	28216
464	27820
465	28172
466	27967
467	27525
468	27838
469	27780
470	27083
471	27181
472	26979
473	27087
474	27070
475	26559
476	26574
477	26400
478	26669
479	25846
480	26113
481	25990
482	25889
483	25858
484	25530
485	25430
486	25550
487	25073
488	24874
489	24967
490	24637
491	24607
492	24441
493	24411
494	24319
495	24061
496	24053
497	24060
498	23762
499	23567
500	23416
501	23423
502	23393
503	23087
504	23288
505	22811
506	22966
507	23147
508	22856
509	22718
510	22855
511	22611
512	22345
513	22376
514	22208
515	22254
516	22097
517	21931
518	22127
519	22054
520	21772
521	21726
522	21651
523	21453
524	21251
525	21046
526	21218
527	20997
528	20893
529	21057
530	20827
531	21041
532	20553
533	20513
534	20152
535	20413
536	20181
537	20250
538	20028
539	20130
540	20182
541	20136
542	20204
543	20111
544	19848
545	19997
546	19423
547	19453
548	19348
549	19284
550	19102
551	19052
552	18929
553	19158
554	18884
555	18893
556	18815
557	18566
558	18715
559	18530
560	18517
561	18403
562	18423
563	18490
564	18223
565	18289
566	17880
567	18132
568	17984
569	18039
570	17856
571	17926
572	17739
573	17650
574	17371
575	17513
576	17325
577	17119
578	17197
579	17401
580	17358
581	17427
582	17164
583	17276
584	17025
585	16908
586	16982
587	16900
588	16767
589	16709
590	16582
591	16498
592	16630
593	16535
594	16725
595	16581
596	16356
597	16160
598	16192
599	16162
600	16343
601	15944
602	16047
603	15867
604	16015
605	15669
606	15588
607	15846
608	15588
609	15472
610	15584
611	15178
612	15341
613	15265
614	15295
615	15194
616	15044
617	15160
618	14978
619	15190
620	15216
621	14969
622	14998
623	14821
624	14960
625	14562
626	14723
627	14510
628	14676
629	14343
630	14421
631	14530
632	14205
633	14008
634	14174
635	14304
636	14171
637	14106
638	14074
639	13791
640	13875
641	13745
642	13701
643	13817
644	13694
645	13755
646	13498
647	13713
648	13589
649	13641
650	13627
651	13296
652	13309
653	13358
654	13174
655	12876
656	13074
657	13065
658	13172
659	13045
660	13277
661	13116
662	13124
663	12849
664	13071
665	13028
666	12834
667	12658
668	12791
669	12849
670	12608
671	12513
672	12671
673	12528
674	12414
675	12581
676	12513
677	12461
678	12460
679	12534
680	12390
681	12464
682	12264
683	12280
684	12115
685	12155
686	12032
687	12020
688	12067
689	11764
690	11814
691	11864
692	11952
693	11958
694	11728
695	11746
696	11685
697	11626
698	11580
699	11546
700	11604
701	11488
702	11298
703	11644
704	11341
705	11420
706	11386
707	11228
708	11331
709	11264
710	11023
711	11208
712	11122
713	11149
714	10997
715	11008
716	10955
717	11050
718	10997
719	10992
720	10778
721	10907
722	10940
723	10855
724	10944
725	10817
726	10853
727	10743
728	10689
729	10524
730	10655
731	10712
732	10537
733	10543
734	10584
735	10530
736	10558
737	10433
738	10494
739	10347
740	10305
741	10386
742	10447
743	10242
744	10240
745	10268
746	10175
747	10263
748	9944
749	10035
750	10033
751	10007
752	9952
753	10007
754	9895
755	9716
756	9722
757	9819
758	9784
759	9611
760	9737
761	9622
762	9435
763	9464
764	9634
765	9457
766	9544
767	9556
768	9603
769	9456
770	9553
771	9362
772	9309
773	9427
774	9535
775	9293
776	9364
777	9302
778	9173
779	9148
780	9106
781	9094
782	9106
783	9106
784	9095
785	9100
786	8965
787	9063
788	8937
789	9039
790	8880
791	8850
792	8980
793	8906
794	8890
795	8798
796	8631
797	8704
798	8637
799	8614
800	8604
801	8563
802	8650
803	8552
804	8586
805	8624
806	8553
807	8429
808	8497
809	8349
810	8487
811	8502
812	8408
813	8407
814	8430
815	8493
816	8283
817	8352
818	8450
819	8426
820	8302
821	8558
822	8267
823	8245
824	8095
825	8206
826	8128
827	8132
828	8095
829	8168
830	8056
831	8058
832	8091
833	8140
834	8034
835	7891
836	7809
837	7932
838	7926
839	7733
840	7932
841	7674
842	7779
843	7706
844	7831
845	7802
846	7828
847	7733
848	7799
849	7822
850	7777
851	7638
852	7740
853	7767
854	7591
855	7641
856	7548
857	7606
858	7658
859	7555
860	7416
861	7490
862	7666
863	7679
864	7626
865	7579
866	7543
867	7431
868	7320
869	7399
870	7240
871	7326
872	7202
873	7291
874	7471
875	7282
876	7272
877	7248
878	7198
879	7117
880	7166
881	7056
882	7073
883	7093
884	7212
885	6937
886	7044
887	6942
888	7128
889	6914
890	7019
891	6964
892	7000
893	7075
894	6950
895	6964
896	6869
897	6845
898	6739
899	6809
900	6687
901	6727
902	6681
903	6781
904	6692
905	6729
906	6544
907	6679
908	6552
909	6602
910	6470
911	6608
912	6520
913	6630
914	6496
915	6646
916	6515
917	6570
918	6523
919	6449
920	6532
921	6425
922	6375
923	6249
924	6293
925	6342
926	6397
927	6342
928	6397
929	6456
930	6211
931	6234
932	6361
933	6382
934	6167
935	6297
936	6330
937	6109
938	6149
939	6141
940	6144
941	6149
942	6062
943	5985
944	6182
945	6039
946	6152
947	5947
948	6003
949	5970
950	6017
951	5983
952	5918
953	5885
954	6022
955	6014
956	5866
957	5894
958	5902
959	5978
960	5950
961	5853
962	5869
963	5851
964	5911
965	5869
966	5935
967	6017
968	5839
969	5747
970	5866
971	5793
972	5833
973	5694
974	5753
975	5654
976	5747
977	5740
978	5793
979	5683
980	5578
981	5626
982	5707
983	5570
984	5497
985	5584
986	5448
987	5567
988	5445
989	5413
990	5491
991	5619
992	5351
993	5579
994	5541
995	5382
996	5498
997	5378
998	5529
999	5521
1000	22876067