1	6732798226
2	855568788
3	195259460
4	78877590
5	37990742
6	24648649
7	16826485
8	12727815
9	10056501
10	8325161
11	7125254
12	6298864
13	5702139
14	5289446
15	4991369
16	4779334
17	4615053
18	4515660
19	4438945
20	4401215
21	4377792
22	4357082
23	4356813
24	4360187
25	4373599
26	4385612
27	4396835
28	4418977
29	4438416
30	4448906
31	4467289
32	4473262
33	4484889
34	4495976
35	4494775
36	4501783
37	4505827
38	4507326
39	4499438
40	4500995
41	4490912
42	4489391
43	4478842
44	4457769
45	4446403
46	4426908
47	4409930
48	4386218
49	4367546
50	4346130
51	4323536
52	4296076
53	4265714
54	4231741
55	4207523
56	4173866
57	4139028
58	4111622
59	4080486
60	4037554
61	4005725
62	3974572
63	3936935
64	3896288
65	3853897
66	3821103
67	3780097
68	3740137
69	3703539
70	3670973
71	3632564
72	3590092
73	3553664
74	3521326
75	3490445
76	3453162
77	3415460
78	3380159
79	3347949
80	3313030
81	3282399
82	3251114
83	3217473
84	3179136
85	3149965
86	3118172
87	3080329
88	3051611
89	3017819
90	2989780
91	2958168
92	2923026
93	2887535
94	2856663
95	2824710
96	2790415
97	2766232
98	2733395
99	2702578
100	2674132
101	2641899
102	2609815
103	2578661
104	2548442
105	2514978
106	2485611
107	2450872
108	2418241
109	2383966
110	2348941
111	2322034
112	2288459
113	2262115
114	2229654
115	2199306
116	2172411
117	2141721
118	2111082
119	2083777
120	2055816
121	2021557
122	1991875
123	1961586
124	1939548
125	1911687
126	1883386
127	1855141
128	1829195
129	1801789
130	1773946
131	1753037
132	1725620
133	1700586
134	1678411
135	1650348
136	1627844
137	1604566
138	1581814
139	1557712
140	1535073
141	1511570
142	1489907
143	1468390
144	1448828
145	1430106
146	1409027
147	1389140
148	1370195
149	1354881
150	1336495
151	1318318
152	1302190
153	1282435
154	1264693
155	1247028
156	1230079
157	1215755
158	1201339
159	1184727
160	1172183
161	1156931
162	1141420
163	1126948
164	1116084
165	1103565
166	1088853
167	1078452
168	1064396
169	1052953
170	1041197
171	1028473
172	1014992
173	1005279
174	993759
175	983808
176	971470
177	961103
178	950931
179	939831
180	930012
181	919590
182	908331
183	899078
184	889544
185	879552
186	870043
187	859244
188	850785
189	840422
190	832962
191	823241
192	815044
193	806241
194	795073
195	786311
196	777716
197	768900
198	761412
199	752383
200	743158
201	734702
202	727890
203	719194
204	711657
205	701868
206	691996
207	684169
208	676122
209	667749
210	662747
211	654502
212	646126
213	637636
214	629127
215	621462
216	614623
217	605078
218	597407
219	591553
220	583920
221	576900
222	567454
223	561255
224	555164
225	547456
226	540346
227	533806
228	526759
229	519401
230	512506
231	505725
232	498480
233	492142
234	485267
235	479484
236	472139
237	465629
238	458312
239	452278
240	445307
241	439894
242	432137
243	426300
244	419394
245	412327
246	406924
247	401030
248	394816
249	389744
250	382947
251	377270
252	370835
253	365607
254	360942
255	354363
256	348862
257	343047
258	337549
259	333231
260	326803
261	321654
262	316149
263	311086
264	305740
265	299858
266	295727
267	291166
268	285607
269	281155
270	276909
271	271940
272	267371
273	263148
274	258601
275	253624
276	249590
277	244170
278	240881
279	236947
280	233577
281	229676
282	227030
283	222960
284	218883
285	214666
286	212149
287	208524
288	204737
289	202463
290	197278
291	194328
292	190799
293	188605
294	185469
295	181595
296	179295
297	176264
298	173060
299	169892
300	168122
301	164766
302	162802
303	159569
304	157057
305	153861
306	151802
307	149133
308	146572
309	143393
310	141758
311	138911
312	136544
313	134457
314	132362
315	129593
316	127481
317	125746
318	124608
319	122402
320	119816
321	117659
322	116711
323	114855
324	113072
325	111603
326	110494
327	107958
328	106376
329	104976
330	103453
331	101770
332	99640
333	98426
334	97323
335	95675
336	94417
337	92173
338	91260
339	90412
340	89120
341	87277
342	86580
343	85312
344	83776
345	82348
346	81612
347	80448
348	79106
349	78285
350	77016
351	76392
352	75295
353	74548
354	74017
355	72396
356	71636
357	70753
358	69643
359	68906
360	68626
361	67489
362	66867
363	66049
364	65305
365	64317
366	63612
367	62784
368	62199
369	60848
370	60074
371	59422
372	58877
373	58584
374	57699
375	56772
376	56618
377	56182
378	55383
379	55340
380	54087
381	53546
382	52565
383	52009
384	52109
385	51084
386	50603
387	50208
388	49520
389	49317
390	49150
391	48230
392	47711
393	47497
394	46966
395	46466
396	45945
397	45908
398	45396
399	44977
400	44431
401	44118
402	43432
403	42405
404	42242
405	42048
406	41478
407	41161
408	40871
409	40332
410	40147
411	39791
412	39495
413	38844
414	38511
415	38258
416	38628
417	37795
418	37415
419	37215
420	36580
421	36595
422	36361
423	35963
424	35737
425	35301
426	35099
427	34654
428	34392
429	34226
430	33802
431	33622
432	33090
433	33114
434	32947
435	32683
436	32349
437	31898
438	31589
439	31635
440	31210
441	31473
442	31142
443	30829
444	30372
445	30238
446	30290
447	30025
448	29740
449	29289
450	28929
451	28945
452	28718
453	28650
454	28434
455	28183
456	27798
457	27584
458	27452
459	26839
460	27439
461	26858
462	26871
463	26514
464	26488
465	26118
466	25918
467	25857
468	25543
469	25501
470	25581
471	25398
472	25126
473	25055
474	24836
475	24693
476	24531
477	24630
478	24010
479	24090
480	24255
481	23942
482	23557
483	23665
484	23028
485	23156
486	23502
487	23001
488	22855
489	22939
490	22453
491	22354
492	22345
493	22106
494	21981
495	21925
496	21794
497	21893
498	21751
499	21549
500	21410
501	21196
502	21184
503	20897
504	20832
505	20560
506	20386
507	20509
508	20468
509	20318
510	20071
511	19942
512	20065
513	19846
514	19936
515	19503
516	19667
517	19485
518	19595
519	19275
520	19395
521	19270
522	19237
523	19131
524	19107
525	18755
526	18604
527	18824
528	18656
529	18551
530	18457
531	18299
532	18054
533	18177
534	18007
535	17907
536	17821
537	17736
538	17658
539	17573
540	17572
541	17298
542	17594
543	17445
544	17279
545	17155
546	17266
547	17041
548	17061
549	17010
550	16823
551	16946
552	16848
553	16537
554	16744
555	16501
556	16454
557	16406
558	16125
559	16224
560	16297
561	16215
562	16307
563	15836
564	15824
565	15887
566	15776
567	15776
568	15677
569	15772
570	15619
571	15881
572	15533
573	15499
574	15422
575	15334
576	15388
577	15106
578	14900
579	15114
580	14899
581	14689
582	14870
583	14862
584	14745
585	15000
586	14662
587	14556
588	14516
589	14568
590	14296
591	14362
592	14270
593	14338
594	14259
595	14164
596	14003
597	14187
598	13999
599	14017
600	14054
601	13698
602	13699
603	13664
604	13673
605	13678
606	13757
607	13409
608	13508
609	13492
610	13417
611	13344
612	13159
613	13344
614	13117
615	13063
616	13252
617	13262
618	13076
619	12836
620	13004
621	12904
622	13182
623	12990
624	12703
625	12814
626	12904
627	12710
628	12857
629	12687
630	12788
631	12679
632	12730
633	12640
634	12325
635	12523
636	12247
637	12415
638	12220
639	12254
640	12146
641	12236
642	12023
643	11941
644	11956
645	12029
646	11886
647	11801
648	11817
649	11685
650	11934
651	12012
652	11787
653	11441
654	11706
655	11701
656	11683
657	11405
658	11435
659	11346
660	11444
661	11382
662	11130
663	11243
664	11134
665	11234
666	11105
667	11176
668	10999
669	11009
670	11114
671	10956
672	10896
673	10980
674	10770
675	10909
676	10718
677	10768
678	10792
679	10587
680	10686
681	10776
682	10550
683	10656
684	10512
685	10448
686	10397
687	10462
688	10389
689	10391
690	10115
691	10292
692	10223
693	10270
694	10284
695	10292
696	10252
697	10361
698	9926
699	9876
700	10115
701	9935
702	9952
703	9770
704	9834
705	9709
706	9677
707	9707
708	9728
709	9643
710	9610
711	9744
712	9616
713	9769
714	9732
715	9335
716	9515
717	9636
718	9611
719	9584
720	9330
721	9535
722	9221
723	9501
724	9360
725	9476
726	9350
727	9500
728	9359
729	9407
730	9359
731	9264
732	9023
733	9159
734	9176
735	9144
736	9103
737	8957
738	8991
739	9160
740	9067
741	8936
742	8754
743	8904
744	8963
745	8906
746	9066
747	8985
748	8991
749	8673
750	8853
751	8746
752	8700
753	8840
754	8720
755	8667
756	8663
757	8629
758	8700
759	8643
760	8812
761	8416
762	8511
763	8685
764	8526
765	8308
766	8485
767	8280
768	8417
769	8381
770	8367
771	8207
772	8350
773	8297
774	8131
775	8230
776	8259
777	8152
778	8073
779	8087
780	7958
781	8060
782	8097
783	7844
784	7980
785	7937
786	7956
787	7922
788	7902
789	8086
790	7867
791	7957
792	8007
793	7972
794	7985
795	7896
796	7790
797	7922
798	7849
799	7950
800	7814
801	7705
802	7809
803	7653
804	7701
805	7698
806	7800
807	7559
808	7567
809	7531
810	7679
811	7527
812	7432
813	7510
814	7495
815	7421
816	7368
817	7323
818	7150
819	7313
820	7269
821	7275
822	7181
823	7298
824	7220
825	7355
826	7156
827	7259
828	7108
829	7023
830	7223
831	7175
832	7135
833	7282
834	7147
835	7129
836	7076
837	7062
838	7244
839	7078
840	7052
841	6931
842	7032
843	6939
844	6921
845	6826
846	6798
847	6991
848	6721
849	6860
850	6806
851	6807
852	6654
853	6657
854	6759
855	6620
856	6600
857	6719
858	6656
859	6574
860	6626
861	6491
862	6555
863	6502
864	6786
865	6574
866	6618
867	6561
868	6531
869	6511
870	6357
871	6717
872	6348
873	6570
874	6524
875	6497
876	6413
877	6377
878	6342
879	6278
880	6386
881	6313
882	6333
883	6273
884	6146
885	6243
886	6243
887	6120
888	6213
889	6345
890	6130
891	6266
892	6333
893	6118
894	6145
895	6244
896	6070
897	6299
898	6041
899	6008
900	6108
901	6111
902	6105
903	6050
904	6178
905	6068
906	6093
907	6067
908	6063
909	5941
910	5796
911	5912
912	5960
913	5896
914	5954
915	5838
916	5839
917	5969
918	5884
919	5847
920	5609
921	5706
922	5717
923	5705
924	5693
925	5830
926	5821
927	5772
928	5788
929	5596
930	5641
931	5709
932	5617
933	5672
934	5703
935	5662
936	5518
937	5670
938	5557
939	5625
940	5524
941	5654
942	5576
943	5611
944	5646
945	5601
946	5401
947	5608
948	5398
949	5475
950	5464
951	5562
952	5524
953	5463
954	5489
955	5357
956	5592
957	5556
958	5446
959	5367
960	5334
961	5335
962	5302
963	5273
964	5314
965	5309
966	5420
967	5311
968	5384
969	5281
970	5249
971	5270
972	5160
973	5212
974	5266
975	5003
976	5184
977	5115
978	5154
979	5120
980	5165
981	5099
982	5030
983	5057
984	4889
985	4972
986	5152
987	5111
988	5003
989	5007
990	4982
991	5002
992	5120
993	4984
994	5027
995	5037
996	4975
997	5080
998	4949
999	4961
1000	20735399