1	3834007766
2	318075302
3	82521355
4	32823558
5	16946242
6	10733274
7	7495302
8	5887736
9	4743946
10	4184301
11	3668893
12	3441923
13	3169132
14	3104473
15	2991050
16	3021856
17	2974921
18	3059232
19	3049290
20	3188630
21	3220331
22	3363824
23	3433179
24	3607587
25	3715911
26	3879414
27	3984581
28	4131818
29	4209144
30	4283214
31	4319050
32	4365578
33	4340026
34	4319309
35	4236921
36	4154156
37	4039900
38	3958726
39	3797168
40	3689919
41	3537375
42	3417746
43	3257556
44	3149149
45	3012046
46	2895642
47	2786527
48	2705325
49	2632403
50	2561255
51	2490016
52	2456612
53	2390235
54	2375476
55	2332430
56	2306019
57	2292851
58	2284817
59	2256351
60	2234455
61	2216333
62	2213535
63	2192377
64	2183668
65	2153521
66	2135573
67	2112906
68	2095481
69	2063358
70	2034629
71	2012672
72	1982566
73	1948090
74	1914102
75	1888796
76	1855142
77	1834579
78	1801685
79	1768681
80	1737793
81	1721613
82	1698503
83	1673495
84	1650113
85	1632139
86	1616181
87	1600692
88	1586922
89	1574165
90	1561637
91	1550571
92	1540520
93	1540985
94	1532993
95	1528371
96	1518642
97	1515204
98	1513485
99	1506336
100	1500671
101	1501337
102	1496903
103	1500510
104	1495949
105	1490059
106	1489495
107	1491767
108	1489345
109	1483144
110	1479403
111	1478819
112	1475139
113	1477142
114	1476174
115	1469092
116	1461649
117	1465431
118	1460074
119	1457879
120	1451342
121	1451328
122	1450216
123	1442733
124	1439340
125	1437655
126	1436575
127	1436724
128	1433642
129	1432473
130	1430153
131	1424478
132	1425365
133	1424227
134	1418115
135	1422551
136	1414120
137	1412116
138	1407707
139	1400856
140	1401670
141	1401369
142	1395563
143	1392185
144	1385584
145	1380601
146	1376462
147	1376996
148	1371386
149	1365036
150	1360262
151	1358979
152	1356193
153	1352914
154	1348906
155	1350707
156	1344483
157	1343146
158	1335529
159	1331911
160	1332641
161	1324059
162	1320641
163	1310727
164	1308538
165	1309595
166	1302201
167	1297751
168	1290827
169	1288018
170	1283762
171	1274793
172	1273133
173	1268047
174	1260253
175	1259796
176	1254911
177	1255601
178	1249791
179	1235444
180	1231667
181	1230925
182	1225376
183	1221395
184	1215830
185	1209378
186	1205432
187	1200035
188	1193565
189	1187095
190	1179824
191	1174997
192	1174555
193	1170182
194	1164456
195	1159275
196	1153784
197	1145874
198	1143866
199	1135364
200	1126680
201	1120298
202	1118628
203	1115896
204	1105865
205	1102181
206	1095570
207	1090572
208	1085759
209	1076178
210	1073721
211	1072554
212	1065476
213	1059779
214	1052487
215	1047692
216	1043593
217	1035624
218	1031317
219	1021792
220	1015617
221	1015596
222	1011322
223	1002457
224	999116
225	993979
226	989126
227	977181
228	974714
229	971055
230	964682
231	957170
232	952287
233	946739
234	945748
235	940699
236	930147
237	924108
238	915933
239	908522
240	906027
241	901713
242	896642
243	889846
244	882973
245	878547
246	873533
247	864554
248	862340
249	858455
250	852480
251	847086
252	843371
253	832851
254	825179
255	824560
256	817037
257	812342
258	809112
259	802632
260	797234
261	791128
262	788248
263	783173
264	776239
265	771498
266	765695
267	761745
268	753672
269	747743
270	745732
271	739254
272	736417
273	731362
274	724375
275	718188
276	717426
277	709895
278	704645
279	700710
280	693400
281	689656
282	683417
283	681473
284	677210
285	671162
286	668132
287	661173
288	658595
289	654455
290	647883
291	644565
292	637794
293	631339
294	627894
295	622788
296	619751
297	612609
298	608377
299	602599
300	600745
301	595821
302	590334
303	586675
304	583727
305	577665
306	574946
307	568700
308	565902
309	559077
310	555394
311	550609
312	549239
313	542808
314	537357
315	533667
316	532231
317	527716
318	523611
319	519110
320	515504
321	510817
322	505272
323	501306
324	499364
325	494505
326	490326
327	488229
328	483767
329	479149
330	476992
331	474131
332	471342
333	463992
334	459781
335	458812
336	454659
337	450459
338	448636
339	443070
340	437508
341	436109
342	431679
343	430632
344	424637
345	420612
346	417141
347	414868
348	412233
349	407863
350	406825
351	402856
352	398679
353	397396
354	393751
355	390698
356	388270
357	383944
358	378373
359	377103
360	374265
361	371918
362	369605
363	364354
364	362796
365	360438
366	356813
367	351586
368	349578
369	347549
370	344900
371	341108
372	340128
373	334493
374	333214
375	329132
376	326802
377	324098
378	321824
379	318466
380	318061
381	315237
382	310478
383	310144
384	308042
385	306928
386	303537
387	300923
388	298112
389	294513
390	292168
391	289990
392	288122
393	285258
394	282140
395	279983
396	277490
397	275678
398	275615
399	273063
400	270816
401	267766
402	265807
403	264025
404	261624
405	259483
406	255800
407	253423
408	251380
409	250322
410	248299
411	245987
412	243357
413	240211
414	240215
415	236801
416	234597
417	232870
418	231687
419	229995
420	227032
421	225709
422	224427
423	221575
424	220262
425	218673
426	215363
427	212546
428	212020
429	211500
430	210551
431	209254
432	207321
433	205564
434	204113
435	202290
436	201390
437	199165
438	197085
439	194966
440	193091
441	191261
442	189533
443	188734
444	187130
445	186313
446	184311
447	183238
448	182479
449	181320
450	176275
451	176721
452	176039
453	175179
454	174150
455	172286
456	169747
457	168648
458	166648
459	164471
460	164733
461	163341
462	160843
463	160313
464	158943
465	157213
466	156245
467	155256
468	154313
469	153332
470	151798
471	150714
472	149926
473	149543
474	147068
475	147018
476	145498
477	144330
478	142372
479	141773
480	140018
481	137967
482	136875
483	136127
484	134773
485	135045
486	133316
487	132176
488	131469
489	130867
490	128850
491	127918
492	127460
493	126440
494	125469
495	124809
496	122922
497	122403
498	121221
499	120113
500	119180
501	118351
502	118510
503	117190
504	116920
505	116228
506	114136
507	113965
508	113984
509	112854
510	111406
511	110289
512	109460
513	109135
514	107314
515	105572
516	105571
517	103804
518	104097
519	103128
520	102429
521	101612
522	100810
523	100316
524	98977
525	99054
526	97488
527	96878
528	96183
529	95490
530	94829
531	94228
532	92946
533	93585
534	93039
535	92161
536	91488
537	90869
538	90274
539	89013
540	88849
541	88132
542	86657
543	86875
544	85850
545	83918
546	84113
547	83185
548	83232
549	82295
550	82225
551	81375
552	80977
553	80978
554	79982
555	79263
556	78952
557	78059
558	76993
559	76129
560	76036
561	76366
562	75155
563	74901
564	73851
565	73875
566	72949
567	73231
568	71540
569	72381
570	71317
571	71291
572	70696
573	70223
574	69316
575	68569
576	67533
577	67300
578	67030
579	66236
580	66077
581	65011
582	65262
583	64820
584	64614
585	64180
586	64238
587	63505
588	63043
589	62505
590	62044
591	61427
592	60756
593	60855
594	60341
595	60186
596	59103
597	58745
598	58545
599	58177
600	57935
601	57690
602	57029
603	56442
604	56259
605	55933
606	55239
607	54870
608	54651
609	54559
610	53407
611	53663
612	53558
613	52454
614	52817
615	52291
616	51499
617	51404
618	51490
619	50833
620	50556
621	50526
622	49859
623	49617
624	49504
625	49516
626	48968
627	48173
628	48198
629	47484
630	47327
631	46899
632	46809
633	47320
634	46928
635	46470
636	45907
637	45943
638	45166
639	45701
640	44735
641	44157
642	44163
643	43898
644	43463
645	43573
646	43358
647	43119
648	42903
649	42680
650	42221
651	41849
652	41686
653	41263
654	40792
655	40935
656	40933
657	40548
658	40645
659	40017
660	39910
661	39213
662	38719
663	39160
664	38725
665	38394
666	37858
667	37934
668	37899
669	37892
670	37279
671	37220
672	37142
673	36761
674	36437
675	36565
676	36635
677	36190
678	35633
679	35565
680	35711
681	35352
682	35105
683	34507
684	34128
685	34767
686	34463
687	33918
688	33472
689	33578
690	33333
691	33216
692	33000
693	32986
694	32719
695	32605
696	32268
697	31770
698	31764
699	31936
700	31698
701	31710
702	31184
703	31243
704	31107
705	30859
706	30591
707	30703
708	30588
709	30418
710	30358
711	29927
712	30135
713	29683
714	29707
715	29509
716	29172
717	29054
718	28587
719	28498
720	28541
721	28644
722	28078
723	27960
724	27760
725	27712
726	27634
727	28022
728	27325
729	27167
730	27542
731	26915
732	26521
733	26296
734	26332
735	26412
736	26356
737	26140
738	26167
739	26200
740	25590
741	25769
742	25433
743	25486
744	25456
745	25227
746	24749
747	24877
748	24954
749	25217
750	24790
751	24646
752	24612
753	24613
754	24172
755	24190
756	23946
757	24000
758	23398
759	23428
760	23241
761	23451
762	22919
763	22673
764	22849
765	22767
766	22753
767	22715
768	22269
769	22356
770	22326
771	21904
772	22388
773	22524
774	22160
775	22017
776	21873
777	21524
778	21434
779	21303
780	21472
781	21292
782	21329
783	21019
784	20890
785	20914
786	20846
787	20727
788	20660
789	20520
790	20305
791	20444
792	20595
793	20548
794	20125
795	19857
796	19811
797	19891
798	19595
799	19641
800	19766
801	19529
802	19663
803	19589
804	19300
805	19503
806	19117
807	18938
808	18964
809	18888
810	19041
811	18656
812	18211
813	18366
814	18613
815	18433
816	18349
817	17858
818	17919
819	17948
820	17863
821	17935
822	17926
823	17650
824	17744
825	17665
826	17388
827	17514
828	17727
829	17764
830	17420
831	17290
832	17605
833	17412
834	17097
835	16927
836	16865
837	16975
838	16891
839	17030
840	16468
841	16364
842	16235
843	16347
844	16191
845	16316
846	16287
847	16388
848	16249
849	15899
850	15936
851	15655
852	15755
853	15777
854	16077
855	15634
856	15881
857	15634
858	15278
859	15561
860	15423
861	15398
862	15116
863	15298
864	15013
865	14853
866	14767
867	15038
868	14950
869	14783
870	14844
871	14683
872	14942
873	14954
874	14622
875	14744
876	14801
877	14533
878	14096
879	14035
880	14007
881	14054
882	13547
883	13975
884	13890
885	13984
886	13962
887	13598
888	13913
889	13732
890	13673
891	13715
892	13525
893	13560
894	13499
895	13322
896	13309
897	13282
898	13173
899	13177
900	13356
901	13414
902	13168
903	13037
904	13163
905	12939
906	12833
907	12666
908	12688
909	12933
910	12989
911	12667
912	12676
913	12600
914	12845
915	12746
916	12674
917	12627
918	12544
919	12409
920	12319
921	11938
922	12231
923	12198
924	12213
925	12188
926	12224
927	12000
928	11866
929	11926
930	11776
931	12054
932	11960
933	11892
934	11711
935	11661
936	11829
937	11899
938	11973
939	11816
940	11541
941	11565
942	11358
943	11657
944	11331
945	11070
946	11359
947	11554
948	11339
949	11283
950	11178
951	11099
952	11014
953	11081
954	11376
955	10991
956	10995
957	10875
958	10973
959	10991
960	10911
961	10947
962	10837
963	10822
964	10638
965	10358
966	10645
967	10843
968	10711
969	10567
970	10419
971	10433
972	10301
973	10476
974	10458
975	10274
976	10340
977	10269
978	10098
979	10131
980	9956
981	10091
982	10037
983	10011
984	10086
985	9989
986	9692
987	9824
988	9858
989	9739
990	9889
991	9612
992	9897
993	9734
994	9581
995	9752
996	9849
997	9728
998	9726
999	9780
1000	21981424