1	2916496026
2	408725532
3	209705310
4	147402554
5	107791568
6	76030799
7	50902664
8	32299155
9	19690414
10	12167034
11	8069490
12	6088405
13	5212026
14	5101583
15	5397740
16	6008643
17	6878763
18	8031678
19	9324295
20	10763015
21	12214255
22	13692539
23	14982043
24	16044089
25	16783103
26	17219791
27	17178513
28	16782018
29	16028323
30	15082545
31	14018143
32	12941519
33	11877615
34	10983222
35	10368970
36	9995364
37	9880136
38	10124518
39	10623576
40	11385948
41	12384507
42	13596425
43	14965570
44	16454637
45	18034231
46	19669389
47	21168048
48	22549933
49	23739107
50	24721165
51	25423341
52	25848608
53	25909554
54	25600956
55	25018986
56	24216796
57	23142002
58	21843958
59	20355144
60	18764477
61	17159174
62	15447710
63	13767257
64	12123542
65	10558730
66	9139843
67	7830184
68	6677687
69	5655940
70	4783971
71	4056576
72	3462403
73	2981134
74	2609123
75	2319656
76	2091479
77	1920357
78	1795747
79	1698902
80	1622667
81	1574440
82	1529110
83	1504391
84	1479717
85	1472520
86	1458844
87	1457658
88	1451398
89	1439939
90	1442379
91	1444608
92	1449739
93	1457297
94	1462560
95	1481195
96	1488650
97	1511878
98	1533768
99	1554230
100	1566891
101	1587824
102	1597145
103	1606504
104	1613454
105	1620691
106	1619487
107	1609684
108	1597189
109	1576690
110	1555145
111	1522845
112	1481819
113	1444114
114	1394299
115	1344527
116	1281390
117	1231565
118	1175138
119	1119940
120	1068891
121	1016850
122	971248
123	922310
124	875896
125	835619
126	799331
127	764671
128	733351
129	701879
130	680927
131	656964
132	637919
133	616049
134	600407
135	587194
136	574736
137	563849
138	557207
139	550261
140	550272
141	542548
142	537766
143	536457
144	534415
145	530336
146	528383
147	528126
148	527367
149	525948
150	526706
151	525022
152	525789
153	520276
154	521448
155	520367
156	520646
157	515587
158	512021
159	512652
160	508404
161	503829
162	498500
163	494973
164	487649
165	481937
166	473928
167	465577
168	460880
169	451084
170	442209
171	433855
172	426031
173	415886
174	408755
175	399949
176	392117
177	382577
178	372714
179	365604
180	355723
181	350332
182	341943
183	333140
184	328075
185	321323
186	317790
187	311626
188	306853
189	299941
190	298258
191	295968
192	294456
193	292151
194	288247
195	285583
196	284924
197	281716
198	279481
199	278059
200	275764
201	272808
202	270714
203	269592
204	268677
205	266593
206	265911
207	260728
208	259283
209	258294
210	255518
211	253608
212	251379
213	249068
214	248736
215	245290
216	244359
217	241882
218	239899
219	239389
220	238754
221	235541
222	231832
223	230192
224	228625
225	226946
226	223518
227	220988
228	218636
229	216962
230	213616
231	210806
232	209814
233	206410
234	202952
235	201030
236	199760
237	194694
238	192269
239	190596
240	189201
241	186446
242	184475
243	182275
244	179384
245	177806
246	177308
247	178040
248	174044
249	173183
250	172003
251	169759
252	168145
253	167310
254	165416
255	162809
256	162241
257	160926
258	159009
259	158767
260	157241
261	157124
262	156711
263	154233
264	153440
265	153197
266	152583
267	151033
268	151118
269	150149
270	147568
271	147728
272	146182
273	144804
274	143935
275	144559
276	141573
277	139659
278	138869
279	137068
280	136218
281	135138
282	133658
283	132992
284	132735
285	130757
286	130614
287	129576
288	129286
289	128177
290	126914
291	125709
292	124213
293	123577
294	122176
295	120725
296	120107
297	120134
298	118506
299	117431
300	116857
301	115188
302	114649
303	113371
304	112221
305	111757
306	110905
307	110575
308	109839
309	109016
310	108310
311	106193
312	106944
313	107016
314	106349
315	104935
316	104181
317	103739
318	103637
319	103613
320	102228
321	101256
322	102031
323	100418
324	99603
325	99403
326	99435
327	98645
328	97931
329	96227
330	96768
331	95298
332	94645
333	94164
334	93388
335	93190
336	92521
337	91746
338	91305
339	91176
340	90811
341	89725
342	89430
343	88784
344	88075
345	87287
346	86989
347	86188
348	85635
349	84777
350	84327
351	83369
352	83458
353	82914
354	82501
355	81789
356	81514
357	80646
358	80169
359	79991
360	79257
361	78954
362	78554
363	77495
364	77309
365	76550
366	77051
367	76069
368	76009
369	75706
370	74611
371	74729
372	74726
373	74767
374	73400
375	73171
376	72541
377	72427
378	71921
379	71787
380	71424
381	70993
382	70098
383	69467
384	69286
385	68874
386	68639
387	68338
388	68174
389	67666
390	67392
391	67173
392	67159
393	66579
394	66246
395	66702
396	65353
397	64557
398	64634
399	63780
400	63143
401	63492
402	63407
403	62943
404	63010
405	62509
406	62164
407	61884
408	62468
409	61055
410	60824
411	60780
412	60555
413	60098
414	59580
415	59671
416	58935
417	58740
418	57997
419	58327
420	58186
421	57731
422	57247
423	56362
424	57197
425	56519
426	56172
427	56157
428	56170
429	55367
430	55236
431	55325
432	54743
433	54836
434	54169
435	53884
436	53409
437	52954
438	52418
439	52866
440	52786
441	52424
442	51869
443	51905
444	51529
445	51026
446	51544
447	50919
448	50421
449	50028
450	50399
451	49980
452	50022
453	49915
454	49135
455	49099
456	49177
457	48837
458	48134
459	48336
460	48170
461	48143
462	48172
463	48221
464	47575
465	47421
466	47243
467	47164
468	46832
469	46568
470	45936
471	46152
472	46041
473	45524
474	45667
475	45624
476	45269
477	45000
478	44833
479	44450
480	44587
481	44268
482	44133
483	44330
484	44041
485	44000
486	43698
487	43752
488	43849
489	43288
490	43052
491	42749
492	43027
493	42511
494	42753
495	42092
496	41740
497	41508
498	41492
499	41455
500	41340
501	40963
502	40657
503	40100
504	40363
505	40778
506	40335
507	39804
508	39788
509	39726
510	39159
511	39288
512	38823
513	38741
514	39160
515	38419
516	38658
517	38616
518	38167
519	38440
520	37587
521	37939
522	37334
523	37337
524	37212
525	36859
526	36237
527	36043
528	36428
529	36058
530	35878
531	35905
532	35622
533	35302
534	35451
535	35426
536	35049
537	34710
538	34802
539	34942
540	34839
541	33985
542	33887
543	34334
544	33855
545	33905
546	34421
547	33922
548	33943
549	33421
550	33785
551	33371
552	32963
553	33141
554	32721
555	32854
556	32771
557	32338
558	32267
559	31919
560	31522
561	31711
562	32021
563	32038
564	31638
565	31265
566	31390
567	31164
568	30927
569	30684
570	31404
571	31050
572	31026
573	30740
574	30410
575	30639
576	30324
577	30340
578	29938
579	30291
580	29874
581	29897
582	29759
583	29555
584	29657
585	29524
586	29395
587	29027
588	28923
589	28967
590	29264
591	28576
592	28638
593	28371
594	28020
595	28369
596	28346
597	28022
598	28090
599	27889
600	27466
601	27641
602	27438
603	27315
604	26997
605	27331
606	27286
607	26941
608	26900
609	26607
610	26602
611	26629
612	26659
613	26196
614	26238
615	26147
616	26054
617	26272
618	26231
619	26182
620	25997
621	25497
622	26061
623	25925
624	25385
625	25400
626	25400
627	25362
628	25075
629	25053
630	24932
631	25017
632	24920
633	24725
634	24843
635	24772
636	24681
637	24658
638	24677
639	24254
640	24413
641	23966
642	24055
643	24401
644	24027
645	24070
646	23679
647	23680
648	23402
649	23349
650	23336
651	22890
652	23171
653	23221
654	23139
655	22895
656	22556
657	22735
658	22944
659	22920
660	22801
661	22695
662	22556
663	22776
664	22655
665	22517
666	22423
667	22351
668	22632
669	22085
670	22310
671	22311
672	22016
673	22059
674	22089
675	22223
676	21771
677	21982
678	21791
679	21421
680	21452
681	21312
682	20990
683	21101
684	21298
685	21496
686	21247
687	20984
688	20967
689	20804
690	20921
691	21048
692	20670
693	20754
694	20485
695	20765
696	20200
697	20437
698	19997
699	20139
700	19921
701	20041
702	20153
703	20256
704	20255
705	19981
706	19679
707	19646
708	19626
709	19684
710	19514
711	19451
712	19105
713	18986
714	19064
715	19508
716	19189
717	19225
718	19644
719	19409
720	19359
721	19031
722	19483
723	18917
724	18648
725	18913
726	18605
727	18720
728	18563
729	18742
730	18437
731	18590
732	18389
733	18383
734	18273
735	18076
736	18040
737	17966
738	17747
739	17954
740	18018
741	18268
742	18500
743	17995
744	17723
745	17777
746	17761
747	17455
748	17651
749	17452
750	17525
751	17580
752	17455
753	17367
754	17365
755	17412
756	17388
757	17317
758	17475
759	17229
760	17104
761	17238
762	17076
763	16839
764	17221
765	16926
766	16727
767	16699
768	16612
769	16203
770	16472
771	16630
772	16665
773	16433
774	16324
775	16195
776	16206
777	16408
778	15960
779	15889
780	16222
781	15979
782	16135
783	16062
784	16078
785	16102
786	15608
787	15842
788	15902
789	15655
790	15771
791	15610
792	15716
793	15477
794	15372
795	15453
796	15693
797	15077
798	15363
799	15444
800	15338
801	15403
802	15424
803	14906
804	14911
805	15054
806	14996
807	14990
808	15021
809	14868
810	14846
811	14643
812	14773
813	14740
814	14797
815	14693
816	14892
817	14645
818	14574
819	14729
820	14347
821	14265
822	14245
823	14174
824	13880
825	14147
826	14153
827	13910
828	14105
829	13889
830	14195
831	14061
832	13831
833	14082
834	14001
835	14000
836	14180
837	13810
838	13938
839	13889
840	13878
841	13630
842	13799
843	13568
844	13698
845	13788
846	13744
847	13880
848	13183
849	13530
850	13376
851	13274
852	13548
853	13524
854	13442
855	13280
856	13214
857	13091
858	13083
859	13136
860	13144
861	13143
862	13063
863	12746
864	12983
865	12847
866	13109
867	12793
868	12716
869	12662
870	12579
871	12885
872	12657
873	12716
874	12883
875	12736
876	12643
877	12541
878	12605
879	12471
880	12478
881	12542
882	12662
883	12672
884	12327
885	12498
886	12633
887	12493
888	12608
889	12312
890	12253
891	12399
892	12407
893	12507
894	12360
895	12224
896	11928
897	12159
898	12080
899	12185
900	12002
901	11823
902	11824
903	11591
904	11838
905	11683
906	11911
907	12098
908	11691
909	11674
910	11626
911	11637
912	11548
913	11646
914	11440
915	11614
916	11345
917	11722
918	11490
919	11121
920	11340
921	11464
922	11375
923	11431
924	11233
925	11286
926	11339
927	11211
928	11373
929	11317
930	11186
931	10977
932	10986
933	10801
934	11007
935	11072
936	10875
937	10795
938	10959
939	10809
940	11046
941	10791
942	10826
943	10657
944	10832
945	10915
946	10634
947	10724
948	10707
949	10590
950	10756
951	10432
952	10461
953	10705
954	10458
955	10578
956	10702
957	10597
958	10475
959	10318
960	10403
961	10338
962	10556
963	10661
964	10440
965	10410
966	10349
967	10014
968	10233
969	10217
970	10335
971	10482
972	10198
973	10198
974	10182
975	10144
976	10051
977	10098
978	10244
979	10142
980	10135
981	10141
982	10160
983	10087
984	9900
985	9930
986	9761
987	9562
988	9887
989	10006
990	9657
991	10002
992	9801
993	9678
994	9679
995	9483
996	9739
997	9809
998	9742
999	9641
1000	73120554