1	2562649786
2	367798375
3	240697525
4	237992786
5	241827942
6	234830201
7	218134001
8	197111652
9	176899072
10	158473734
11	141299259
12	124318100
13	106960654
14	89340152
15	72175477
16	56429904
17	42632769
18	31555942
19	23054776
20	16754116
21	12395654
22	9439002
23	7433684
24	6097466
25	5142408
26	4485389
27	3975305
28	3557099
29	3204872
30	2922489
31	2662142
32	2465298
33	2267181
34	2101462
35	1951172
36	1826131
37	1700918
38	1605534
39	1518147
40	1436544
41	1370513
42	1319033
43	1263140
44	1224121
45	1188322
46	1153912
47	1130844
48	1119317
49	1117211
50	1120666
51	1133864
52	1158140
53	1196028
54	1255366
55	1327608
56	1423319
57	1535196
58	1679378
59	1841779
60	2041924
61	2273913
62	2545724
63	2845916
64	3192217
65	3558417
66	3978794
67	4409903
68	4869963
69	5344525
70	5842454
71	6348892
72	6820184
73	7271225
74	7691111
75	8066313
76	8373347
77	8587070
78	8751679
79	8830308
80	8851439
81	8781468
82	8626018
83	8394165
84	8104198
85	7759160
86	7353051
87	6890428
88	6399215
89	5913476
90	5419896
91	4937562
92	4443725
93	3955271
94	3509601
95	3094191
96	2705613
97	2347763
98	2024798
99	1749816
100	1494935
101	1278540
102	1095968
103	930323
104	792148
105	681159
106	591673
107	525897
108	470934
109	429742
110	396871
111	375322
112	359899
113	348244
114	341570
115	342635
116	345274
117	350481
118	359707
119	373703
120	394502
121	416411
122	435041
123	464018
124	497103
125	532210
126	575806
127	621371
128	673866
129	734187
130	795473
131	865147
132	945108
133	1029841
134	1121374
135	1219805
136	1328341
137	1447337
138	1577398
139	1721295
140	1868082
141	2030078
142	2186215
143	2357367
144	2533771
145	2725161
146	2908439
147	3109899
148	3305686
149	3506386
150	3697051
151	3866799
152	4046217
153	4208782
154	4354495
155	4490188
156	4618383
157	4713939
158	4787376
159	4866712
160	4912532
161	4950301
162	4972030
163	4949126
164	4918518
165	4878848
166	4807911
167	4713627
168	4605794
169	4480581
170	4340919
171	4193377
172	4031765
173	3853435
174	3649388
175	3453971
176	3255204
177	3045560
178	2843451
179	2653088
180	2460698
181	2278467
182	2105991
183	1931535
184	1770453
185	1606315
186	1455295
187	1312885
188	1179316
189	1055232
190	937800
191	835503
192	737160
193	649665
194	571749
195	502884
196	443036
197	389339
198	346389
199	311810
200	278474
201	250206
202	230977
203	212465
204	198497
205	185131
206	173585
207	165662
208	158265
209	153253
210	147742
211	145369
212	144767
213	142477
214	142364
215	143800
216	143562
217	144486
218	144667
219	147954
220	148791
221	150569
222	154533
223	157346
224	158860
225	161707
226	165628
227	168050
228	170421
229	172957
230	175292
231	176034
232	179015
233	181303
234	180803
235	181921
236	181256
237	181787
238	181078
239	180981
240	180505
241	178928
242	177997
243	177591
244	174751
245	172588
246	171751
247	169999
248	166760
249	164654
250	161337
251	157140
252	152973
253	149985
254	144920
255	140659
256	137036
257	133889
258	130662
259	127127
260	123323
261	117236
262	114650
263	109847
264	106954
265	103235
266	99690
267	95653
268	94248
269	90175
270	88479
271	84973
272	84091
273	82642
274	81175
275	79841
276	78626
277	77931
278	77201
279	77411
280	76443
281	76073
282	75441
283	75777
284	76057
285	75948
286	76214
287	76350
288	77273
289	78767
290	79688
291	80263
292	81017
293	82011
294	83624
295	84255
296	86005
297	88224
298	89421
299	89237
300	90601
301	92113
302	94551
303	95325
304	95986
305	97172
306	97349
307	98522
308	97993
309	100454
310	100311
311	100746
312	101612
313	100583
314	101422
315	101692
316	102667
317	103033
318	103662
319	103144
320	103638
321	102152
322	101904
323	101944
324	102438
325	101301
326	100890
327	99583
328	98758
329	97287
330	96471
331	94373
332	93609
333	91945
334	90519
335	88290
336	86903
337	84571
338	82956
339	81626
340	81354
341	80263
342	77345
343	75610
344	73705
345	71978
346	70412
347	68743
348	66006
349	63619
350	61989
351	61163
352	58769
353	57322
354	56345
355	55213
356	54050
357	52838
358	51940
359	51244
360	49402
361	49076
362	48551
363	48257
364	47228
365	45895
366	45432
367	44590
368	44665
369	43602
370	43496
371	42870
372	42489
373	42198
374	42259
375	41196
376	41207
377	41874
378	41352
379	41689
380	41775
381	41946
382	41613
383	41902
384	41607
385	41541
386	41834
387	41666
388	41972
389	41579
390	41741
391	41905
392	41986
393	41792
394	41817
395	41604
396	41835
397	41446
398	41470
399	41297
400	40965
401	41151
402	40958
403	40580
404	40344
405	40157
406	40281
407	39492
408	39145
409	38570
410	38519
411	38761
412	38677
413	37659
414	37007
415	36753
416	36813
417	36250
418	36159
419	35555
420	34916
421	34322
422	33992
423	33315
424	33341
425	32930
426	32465
427	31936
428	31739
429	31373
430	30927
431	31084
432	30946
433	30141
434	29355
435	29730
436	29240
437	29385
438	28610
439	28610
440	28505
441	28164
442	27647
443	27914
444	27557
445	27559
446	28000
447	27420
448	27756
449	27367
450	27536
451	27559
452	27408
453	27396
454	27190
455	27401
456	27781
457	27413
458	27586
459	27547
460	27935
461	27668
462	27975
463	27884
464	27193
465	27517
466	27724
467	27714
468	27836
469	27633
470	27806
471	27665
472	27560
473	27784
474	27571
475	27393
476	27061
477	27297
478	26541
479	26917
480	27090
481	26920
482	26620
483	25945
484	26077
485	25897
486	26022
487	25910
488	26000
489	25910
490	25592
491	25190
492	25502
493	25044
494	24660
495	24919
496	24444
497	24043
498	24089
499	23734
500	23522
501	22955
502	23413
503	23289
504	22899
505	23037
506	22800
507	22338
508	22205
509	22243
510	22079
511	21863
512	21626
513	21343
514	21486
515	20820
516	20829
517	20664
518	20041
519	19897
520	19671
521	19691
522	19440
523	19232
524	19058
525	18830
526	18573
527	18621
528	18474
529	18610
530	18519
531	18524
532	18244
533	18221
534	18304
535	18309
536	18563
537	18293
538	18159
539	17932
540	17933
541	18009
542	17806
543	18281
544	18056
545	17908
546	17698
547	17428
548	17692
549	17925
550	17570
551	17656
552	16936
553	17133
554	17239
555	17478
556	17536
557	17239
558	17326
559	17264
560	17330
561	17081
562	17576
563	16973
564	16846
565	16843
566	16657
567	16688
568	16586
569	16715
570	16766
571	16688
572	16480
573	16502
574	16294
575	16413
576	16501
577	16032
578	16029
579	16019
580	15965
581	15913
582	15898
583	15532
584	15645
585	15355
586	15354
587	15285
588	15103
589	14964
590	14722
591	14624
592	14482
593	14737
594	14751
595	14700
596	14680
597	14641
598	14410
599	14546
600	14422
601	14482
602	14242
603	13846
604	14176
605	13825
606	14202
607	14391
608	13878
609	13963
610	14355
611	13956
612	14295
613	13829
614	13810
615	13821
616	13977
617	13915
618	13848
619	13977
620	13765
621	13997
622	13636
623	13718
624	13522
625	13725
626	13581
627	13900
628	13639
629	13458
630	13500
631	13567
632	13565
633	13579
634	13655
635	13537
636	13585
637	13250
638	13132
639	13280
640	13300
641	12808
642	13154
643	13096
644	13137
645	13088
646	12862
647	12820
648	12471
649	12522
650	12506
651	12638
652	12528
653	12301
654	12291
655	12180
656	12198
657	12189
658	12415
659	12564
660	12030
661	11873
662	11759
663	11679
664	11659
665	11705
666	11586
667	11762
668	11521
669	11563
670	11398
671	11206
672	11346
673	11134
674	10865
675	11378
676	11210
677	11038
678	10901
679	11087
680	10873
681	11040
682	10871
683	10966
684	10929
685	10612
686	10470
687	10450
688	10472
689	10708
690	10479
691	10368
692	10279
693	10234
694	10022
695	10368
696	10116
697	9850
698	9771
699	9810
700	9982
701	9946
702	9974
703	10153
704	10035
705	9999
706	9767
707	9680
708	9795
709	9826
710	9761
711	9761
712	9725
713	9633
714	9638
715	9342
716	9517
717	9809
718	9701
719	9324
720	9360
721	9342
722	9399
723	9267
724	9423
725	9255
726	9406
727	9189
728	9358
729	9229
730	9193
731	8968
732	9353
733	9192
734	8967
735	9133
736	9045
737	8957
738	8984
739	8926
740	8899
741	8696
742	8908
743	8836
744	8694
745	8717
746	9033
747	8671
748	8799
749	8683
750	8496
751	8536
752	8621
753	8428
754	8328
755	8381
756	8279
757	8163
758	8195
759	8264
760	8284
761	8362
762	8269
763	8256
764	8074
765	8168
766	8223
767	8189
768	8366
769	8366
770	8338
771	8207
772	8215
773	8019
774	8114
775	8253
776	7877
777	7949
778	7888
779	8146
780	8009
781	8070
782	7943
783	7865
784	8025
785	7863
786	8002
787	7988
788	7875
789	7927
790	7876
791	7776
792	7828
793	7683
794	7900
795	7663
796	7858
797	7589
798	7747
799	7775
800	7984
801	7747
802	7441
803	7630
804	7363
805	7531
806	7270
807	7307
808	7427
809	7280
810	7285
811	7059
812	7182
813	7404
814	7369
815	7369
816	7274
817	7077
818	7117
819	7040
820	7166
821	7365
822	7091
823	7245
824	7405
825	7013
826	7076
827	6936
828	6923
829	7084
830	6888
831	6798
832	6738
833	6705
834	6980
835	6953
836	6859
837	6905
838	6838
839	6914
840	6942
841	6779
842	6622
843	6802
844	6637
845	6717
846	6699
847	6698
848	6635
849	6723
850	6745
851	6567
852	6637
853	6721
854	6635
855	6601
856	6680
857	6565
858	6525
859	6610
860	6574
861	6590
862	6411
863	6480
864	6510
865	6475
866	6189
867	6147
868	6224
869	6347
870	6254
871	6330
872	6303
873	6343
874	6227
875	6189
876	6111
877	6165
878	6185
879	6109
880	6198
881	6072
882	6108
883	6007
884	6049
885	5963
886	6091
887	6098
888	5937
889	5962
890	6064
891	6089
892	6098
893	6106
894	5868
895	5677
896	5901
897	5690
898	5836
899	6050
900	5922
901	5940
902	5829
903	5633
904	5643
905	5638
906	5771
907	5748
908	5765
909	5770
910	5794
911	5813
912	5717
913	5772
914	5826
915	5591
916	5713
917	5669
918	5791
919	5577
920	5396
921	5568
922	5522
923	5604
924	5453
925	5479
926	5495
927	5537
928	5433
929	5344
930	5474
931	5525
932	5493
933	5467
934	5329
935	5361
936	5222
937	5372
938	5330
939	5157
940	5412
941	5329
942	5366
943	5257
944	5085
945	5374
946	5265
947	5286
948	5207
949	5117
950	5164
951	5265
952	5209
953	5190
954	5232
955	5203
956	5154
957	5163
958	5090
959	5172
960	5133
961	5186
962	4958
963	5053
964	5140
965	5107
966	5278
967	5094
968	5122
969	5058
970	5064
971	5034
972	4999
973	4794
974	4984
975	4934
976	4893
977	4931
978	5034
979	5073
980	4849
981	4819
982	5104
983	4904
984	4923
985	5014
986	4830
987	4945
988	4954
989	4938
990	4880
991	4799
992	4939
993	4898
994	4881
995	4830
996	4862
997	4816
998	5022
999	4833
1000	35708732