1	2112715233
2	442814195
3	228496337
4	141240273
5	86419660
6	51661610
7	29853295
8	17612352
9	10929751
10	7401919
11	5248767
12	4057005
13	3205158
14	2670160
15	2247354
16	1906630
17	1641651
18	1465006
19	1300011
20	1183784
21	1076048
22	983967
23	901309
24	834630
25	751723
26	678390
27	615590
28	565554
29	520773
30	482740
31	446920
32	415751
33	393146
34	372299
35	359186
36	346598
37	336892
38	332142
39	331261
40	335444
41	331203
42	337757
43	343813
44	350020
45	353798
46	364679
47	369141
48	379814
49	383240
50	394989
51	405697
52	414458
53	429185
54	442715
55	456665
56	471140
57	481989
58	488163
59	499955
60	507413
61	519726
62	532512
63	547556
64	551571
65	550189
66	558005
67	553445
68	567306
69	564552
70	572805
71	576706
72	577884
73	583694
74	586639
75	584003
76	584033
77	582456
78	581140
79	586614
80	587356
81	599198
82	601432
83	605094
84	601727
85	600354
86	593521
87	596577
88	604012
89	604697
90	609476
91	616975
92	623893
93	627094
94	635497
95	639069
96	642410
97	646356
98	657367
99	657171
100	663625
101	666194
102	670029
103	679101
104	684880
105	689808
106	700846
107	705217
108	717253
109	724257
110	735198
111	750573
112	758652
113	771362
114	786935
115	796486
116	803504
117	827775
118	845950
119	859212
120	883367
121	899041
122	924083
123	939518
124	962154
125	981114
126	1002836
127	1026147
128	1061026
129	1087306
130	1116443
131	1143864
132	1177031
133	1208532
134	1240971
135	1274116
136	1314483
137	1350256
138	1400581
139	1437191
140	1477532
141	1525322
142	1570571
143	1623482
144	1676349
145	1730304
146	1780355
147	1832068
148	1898199
149	1956987
150	2012733
151	2075704
152	2131258
153	2186268
154	2257526
155	2307876
156	2362127
157	2413475
158	2474293
159	2527154
160	2571747
161	2638246
162	2684223
163	2732358
164	2781802
165	2821501
166	2865815
167	2901663
168	2935039
169	2971904
170	2987405
171	2988334
172	2992399
173	2977399
174	2960953
175	2940486
176	2918233
177	2889058
178	2847132
179	2817858
180	2762153
181	2697925
182	2636800
183	2566767
184	2483853
185	2397671
186	2316152
187	2221949
188	2136217
189	2055327
190	1965002
191	1874902
192	1775358
193	1684970
194	1595348
195	1508909
196	1420348
197	1331495
198	1249693
199	1175303
200	1101458
201	1030998
202	969447
203	906057
204	845488
205	792031
206	742410
207	691144
208	642499
209	602162
210	562529
211	530766
212	499136
213	472232
214	447719
215	425533
216	407958
217	390978
218	379716
219	370135
220	359550
221	351175
222	343027
223	339132
224	334749
225	331642
226	331252
227	328918
228	327275
229	324969
230	322974
231	323512
232	324546
233	327071
234	327583
235	331969
236	334375
237	339175
238	340174
239	342443
240	343423
241	348441
242	354023
243	359808
244	363617
245	367457
246	375054
247	378914
248	381877
249	388440
250	391619
251	398287
252	403593
253	409201
254	413025
255	420617
256	426236
257	432523
258	438678
259	443642
260	448113
261	454697
262	462961
263	468331
264	474412
265	478841
266	486607
267	490933
268	504214
269	513503
270	519585
271	527590
272	536875
273	539263
274	553243
275	556297
276	568042
277	574362
278	584320
279	593872
280	603857
281	614758
282	624873
283	641203
284	653922
285	663927
286	678018
287	689574
288	700048
289	717333
290	726055
291	738171
292	747804
293	763817
294	773766
295	790002
296	802404
297	813931
298	826117
299	845061
300	858375
301	873382
302	887492
303	899732
304	916821
305	934897
306	951201
307	969850
308	986761
309	1003081
310	1029273
311	1044075
312	1061408
313	1080930
314	1096820
315	1115103
316	1141974
317	1157921
318	1169312
319	1182775
320	1207680
321	1223966
322	1240254
323	1259782
324	1272490
325	1287520
326	1308660
327	1321602
328	1334932
329	1350178
330	1362892
331	1371392
332	1387794
333	1398139
334	1408592
335	1417958
336	1427647
337	1431031
338	1434760
339	1442251
340	1449332
341	1460117
342	1466986
343	1471606
344	1472806
345	1470452
346	1466031
347	1460246
348	1454404
349	1452409
350	1449037
351	1439092
352	1428105
353	1415212
354	1405665
355	1396917
356	1384985
357	1370838
358	1355642
359	1337300
360	1318397
361	1299058
362	1283316
363	1262134
364	1230255
365	1211499
366	1185551
367	1158291
368	1133870
369	1107473
370	1083766
371	1055312
372	1027936
373	994703
374	965979
375	938160
376	907162
377	876590
378	842960
379	809829
380	775281
381	746457
382	715681
383	687902
384	659727
385	630142
386	603725
387	573473
388	547293
389	520358
390	493725
391	466524
392	445406
393	424668
394	402768
395	381042
396	364300
397	343187
398	326329
399	307924
400	293667
401	277128
402	260900
403	246732
404	232992
405	220039
406	206396
407	194526
408	183506
409	172037
410	162522
411	154665
412	146330
413	138357
414	132107
415	125487
416	119003
417	113175
418	107294
419	101540
420	98234
421	93045
422	88915
423	85539
424	82465
425	79683
426	76432
427	73206
428	70904
429	70631
430	70022
431	68551
432	67233
433	65949
434	66044
435	65821
436	65854
437	64827
438	63920
439	62903
440	62276
441	62456
442	61705
443	62461
444	63071
445	62999
446	62798
447	62955
448	62762
449	63473
450	64414
451	63252
452	62972
453	63747
454	64457
455	64164
456	63909
457	65146
458	65689
459	66735
460	66254
461	66399
462	67304
463	67702
464	67501
465	68371
466	69500
467	70106
468	70101
469	69913
470	70687
471	71368
472	71361
473	71225
474	72465
475	72566
476	73818
477	74323
478	74160
479	74854
480	75709
481	75280
482	75027
483	74701
484	75159
485	75717
486	76616
487	77251
488	77306
489	77867
490	78642
491	79188
492	79684
493	80054
494	80873
495	81682
496	82576
497	83950
498	84420
499	84115
500	84740
501	84379
502	85407
503	85677
504	85190
505	85835
506	86081
507	86165
508	87037
509	87543
510	87402
511	88133
512	86992
513	87257
514	87170
515	86426
516	87422
517	87571
518	86830
519	85668
520	85815
521	85178
522	84017
523	83475
524	82791
525	81863
526	81456
527	81063
528	80814
529	80182
530	79281
531	79401
532	77479
533	77275
534	76832
535	75482
536	74777
537	75154
538	74560
539	73260
540	73205
541	71903
542	70825
543	70725
544	69219
545	67790
546	66677
547	66164
548	65646
549	65701
550	65333
551	64637
552	64624
553	63905
554	63901
555	62643
556	61807
557	60489
558	60156
559	58745
560	57266
561	56444
562	55099
563	54674
564	53802
565	52873
566	52251
567	51984
568	51103
569	49993
570	49259
571	48886
572	48516
573	47030
574	46133
575	45630
576	44907
577	44359
578	44359
579	43149
580	43202
581	42721
582	42062
583	41385
584	41399
585	40331
586	40207
587	39683
588	39442
589	38921
590	38572
591	37653
592	37590
593	36923
594	36707
595	36597
596	36246
597	36608
598	36862
599	35792
600	36649
601	36441
602	37330
603	36535
604	36487
605	36851
606	37138
607	36721
608	36576
609	36882
610	37234
611	36838
612	37413
613	38066
614	37635
615	37644
616	37808
617	37982
618	37955
619	38165
620	38497
621	38443
622	38800
623	38811
624	38832
625	38710
626	39551
627	39288
628	39821
629	39490
630	39836
631	39739
632	39984
633	39677
634	40690
635	39880
636	40405
637	39754
638	40571
639	40439
640	40579
641	40556
642	40484
643	40519
644	40601
645	41064
646	40636
647	41025
648	40912
649	40440
650	40963
651	41233
652	41048
653	40961
654	41256
655	41789
656	41322
657	41478
658	41285
659	41697
660	41749
661	41634
662	42053
663	42266
664	42409
665	41784
666	41727
667	42438
668	41967
669	41634
670	41939
671	41781
672	41677
673	42148
674	42200
675	42364
676	42111
677	41793
678	42258
679	41978
680	41501
681	41474
682	41302
683	41444
684	41808
685	41295
686	41570
687	41479
688	41909
689	41981
690	42401
691	42086
692	41859
693	41889
694	41806
695	41677
696	41745
697	41450
698	41147
699	41194
700	41167
701	41690
702	41133
703	40223
704	40776
705	40349
706	39994
707	40296
708	40301
709	39606
710	39252
711	38566
712	38696
713	38766
714	37871
715	38299
716	37551
717	36906
718	37444
719	36794
720	36576
721	35807
722	35479
723	35223
724	34495
725	34502
726	34186
727	33852
728	34041
729	33139
730	32861
731	32857
732	32514
733	32201
734	31840
735	31773
736	31709
737	31339
738	31234
739	31272
740	30799
741	30838
742	29735
743	29692
744	29212
745	28954
746	28701
747	28209
748	27834
749	27227
750	26824
751	27001
752	26840
753	26255
754	25311
755	25279
756	25077
757	24667
758	24527
759	24674
760	24240
761	24337
762	23576
763	23705
764	23435
765	23228
766	22945
767	22753
768	22475
769	22641
770	22449
771	22079
772	21272
773	21500
774	21523
775	21412
776	21119
777	20960
778	20957
779	20680
780	20571
781	20582
782	20055
783	20010
784	20216
785	19942
786	19850
787	19782
788	20027
789	19901
790	19927
791	19594
792	19914
793	19630
794	19820
795	19922
796	19916
797	19878
798	19749
799	19866
800	19749
801	19627
802	20035
803	19993
804	19905
805	19809
806	19937
807	19459
808	19634
809	19596
810	19940
811	19748
812	19458
813	19672
814	19762
815	19935
816	19714
817	19219
818	19770
819	19297
820	19652
821	19631
822	19411
823	19321
824	19321
825	19699
826	19604
827	19427
828	19414
829	19179
830	19212
831	19306
832	19536
833	19124
834	19232
835	19349
836	19360
837	19578
838	19323
839	19032
840	19212
841	19143
842	19074
843	18661
844	18790
845	18744
846	19157
847	19145
848	19372
849	19095
850	19165
851	19103
852	19372
853	19381
854	18727
855	19103
856	18741
857	18612
858	18522
859	18762
860	18935
861	18926
862	18847
863	19084
864	19163
865	19321
866	19122
867	18795
868	18643
869	18489
870	18945
871	18874
872	19180
873	18903
874	18553
875	18810
876	18492
877	18550
878	18577
879	18351
880	18474
881	18339
882	18471
883	18306
884	18445
885	18168
886	18184
887	18324
888	18342
889	18268
890	17768
891	17875
892	17865
893	17600
894	17669
895	17915
896	17898
897	17572
898	17759
899	17421
900	17628
901	17881
902	17750
903	16867
904	17371
905	17039
906	16994
907	17494
908	17020
909	17150
910	17162
911	16851
912	16746
913	16843
914	16736
915	16522
916	16488
917	16000
918	16141
919	15956
920	16099
921	16268
922	15970
923	15836
924	15950
925	15500
926	15608
927	15351
928	15331
929	15116
930	15173
931	15246
932	15117
933	15194
934	15239
935	15236
936	15125
937	15086
938	15188
939	15204
940	14609
941	14482
942	14531
943	14851
944	14677
945	14576
946	14637
947	14812
948	14400
949	14399
950	14328
951	14152
952	14101
953	13977
954	14185
955	14335
956	13835
957	13780
958	13678
959	13733
960	13889
961	13564
962	13429
963	13312
964	13154
965	13385
966	13468
967	13581
968	13415
969	13421
970	13469
971	13394
972	13291
973	13648
974	13766
975	13408
976	13353
977	13448
978	13371
979	13396
980	13088
981	13229
982	13025
983	13167
984	13093
985	13046
986	12658
987	12724
988	12716
989	12873
990	13106
991	12473
992	12529
993	12905
994	12696
995	13075
996	12811
997	12801
998	12658
999	12861
1000	37984660