1	5241770080
2	574820962
3	231502705
4	161732525
5	74394671
6	62522290
7	30012772
8	28258594
9	15290618
10	14889738
11	9469257
12	9150665
13	6747005
14	6440524
15	5333821
16	5101455
17	4576616
18	4406165
19	4139417
20	4024314
21	3895269
22	3821102
23	3740583
24	3701151
25	3654032
26	3629556
27	3608132
28	3596327
29	3571581
30	3561835
31	3545361
32	3526410
33	3511414
34	3498545
35	3478687
36	3466230
37	3448791
38	3430748
39	3407210
40	3381172
41	3355226
42	3333117
43	3302629
44	3276374
45	3243608
46	3203155
47	3166321
48	3133456
49	3100775
50	3059851
51	3018334
52	2982459
53	2944998
54	2901997
55	2861149
56	2830233
57	2784166
58	2745122
59	2699080
60	2658414
61	2620503
62	2578363
63	2530155
64	2489473
65	2448905
66	2415832
67	2371604
68	2323721
69	2286353
70	2243969
71	2208754
72	2172229
73	2130582
74	2089728
75	2054688
76	2017510
77	1984788
78	1942830
79	1906771
80	1869685
81	1837819
82	1802870
83	1770270
84	1734822
85	1709151
86	1676799
87	1641878
88	1613375
89	1582585
90	1551227
91	1525455
92	1492699
93	1470065
94	1439841
95	1410702
96	1387838
97	1365507
98	1341407
99	1319462
100	1291502
101	1266435
102	1245271
103	1220929
104	1201690
105	1179519
106	1154353
107	1135110
108	1112076
109	1091352
110	1072539
111	1051827
112	1034877
113	1016360
114	998411
115	980146
116	960882
117	944779
118	928366
119	911293
120	895976
121	881324
122	865527
123	849310
124	833732
125	819791
126	803527
127	791611
128	777307
129	766104
130	751077
131	739965
132	726735
133	713085
134	700734
135	687686
136	677665
137	664733
138	650534
139	640693
140	630638
141	621695
142	610743
143	599152
144	589767
145	579354
146	570072
147	561899
148	551695
149	542506
150	533129
151	524136
152	516338
153	508309
154	501092
155	493028
156	484221
157	475878
158	469727
159	462789
160	455650
161	448346
162	442881
163	434351
164	427143
165	417445
166	412737
167	407055
168	400601
169	394111
170	387915
171	381838
172	376953
173	370792
174	367488
175	360438
176	355173
177	350084
178	343518
179	338601
180	334836
181	328530
182	326268
183	322065
184	315468
185	311438
186	306622
187	303309
188	299163
189	295088
190	290457
191	285917
192	282553
193	277552
194	273959
195	268893
196	264598
197	262397
198	257408
199	254776
200	251888
201	248373
202	244742
203	240862
204	237949
205	233962
206	230835
207	228116
208	224547
209	221345
210	219048
211	215920
212	212667
213	211201
214	207381
215	204922
216	201837
217	199994
218	197529
219	195306
220	192408
221	188566
222	186559
223	184119
224	182494
225	180057
226	177679
227	175892
228	173871
229	172119
230	169683
231	167553
232	166999
233	163860
234	161961
235	160114
236	157307
237	155629
238	153987
239	151672
240	150049
241	147876
242	145957
243	144019
244	143792
245	141117
246	139860
247	138748
248	136692
249	135425
250	133965
251	132084
252	130414
253	128712
254	128125
255	126151
256	125145
257	123551
258	121410
259	120595
260	120255
261	118594
262	116624
263	115706
264	114000
265	113362
266	112054
267	110883
268	110032
269	108886
270	106577
271	106044
272	104639
273	102997
274	102614
275	101300
276	100449
277	99714
278	98837
279	97412
280	96851
281	95961
282	93636
283	93928
284	93250
285	91690
286	90746
287	89421
288	88562
289	88599
290	87005
291	86687
292	86093
293	84803
294	84044
295	83235
296	82687
297	81813
298	81242
299	80677
300	79923
301	79162
302	78374
303	77180
304	76815
305	75364
306	75356
307	74861
308	73696
309	73596
310	72373
311	71858
312	71701
313	70370
314	70073
315	69173
316	68461
317	67718
318	67336
319	66772
320	65974
321	65509
322	64794
323	63921
324	63600
325	62959
326	63389
327	61438
328	61277
329	61088
330	60545
331	60294
332	59611
333	58585
334	58554
335	57634
336	57411
337	56551
338	56148
339	56112
340	55716
341	54798
342	54808
343	54325
344	54239
345	53129
346	52516
347	52360
348	52187
349	51191
350	51241
351	50741
352	50405
353	50290
354	49460
355	49335
356	48923
357	48446
358	47922
359	47753
360	47245
361	47108
362	46223
363	46393
364	45770
365	45637
366	45311
367	44427
368	44572
369	43768
370	43241
371	43358
372	43188
373	42655
374	42670
375	42257
376	41610
377	41484
378	41334
379	40850
380	40792
381	40717
382	40723
383	40004
384	39531
385	39003
386	39085
387	38567
388	38341
389	38401
390	38120
391	38025
392	37874
393	37391
394	36951
395	36785
396	36232
397	35954
398	35660
399	35741
400	35343
401	34846
402	35049
403	34387
404	34317
405	34450
406	33772
407	33905
408	33448
409	33408
410	33238
411	32780
412	32919
413	32688
414	32184
415	32129
416	31777
417	31588
418	31686
419	31630
420	31219
421	30737
422	30897
423	30747
424	30572
425	30164
426	30103
427	29705
428	29684
429	29352
430	29191
431	29152
432	29144
433	28490
434	28840
435	28817
436	28619
437	28415
438	27867
439	27635
440	27452
441	27325
442	27363
443	27244
444	26785
445	27015
446	27027
447	26731
448	26335
449	26318
450	26009
451	25990
452	25607
453	25783
454	25783
455	25204
456	25379
457	25160
458	25080
459	24766
460	24788
461	24674
462	24512
463	24358
464	24173
465	24065
466	24324
467	24128
468	23821
469	23759
470	23347
471	23400
472	23501
473	23378
474	23353
475	23524
476	22947
477	22955
478	22946
479	22433
480	22549
481	22342
482	22308
483	22369
484	22420
485	22131
486	22306
487	21802
488	21680
489	21610
490	21445
491	21466
492	21353
493	21274
494	21135
495	21127
496	20763
497	20833
498	20554
499	20644
500	20613
501	20274
502	20446
503	20057
504	20211
505	19839
506	19943
507	19988
508	19660
509	19382
510	19416
511	19465
512	19460
513	19357
514	19105
515	19324
516	19085
517	18901
518	18780
519	18654
520	18677
521	18334
522	18325
523	18548
524	18273
525	18379
526	18181
527	17875
528	17887
529	18139
530	17693
531	17393
532	17621
533	17597
534	17768
535	17558
536	17291
537	17312
538	17234
539	16918
540	16971
541	17178
542	16976
543	16883
544	16944
545	16542
546	16707
547	16919
548	16759
549	16639
550	16549
551	16409
552	16308
553	16215
554	16219
555	16022
556	15978
557	16133
558	16097
559	15996
560	15830
561	15699
562	15806
563	15602
564	15749
565	15515
566	15813
567	15448
568	15132
569	15191
570	15221
571	15401
572	15395
573	15053
574	15063
575	15141
576	14727
577	15111
578	14887
579	14641
580	14696
581	14663
582	14587
583	14581
584	14642
585	14306
586	14428
587	14257
588	14128
589	14269
590	14185
591	14358
592	13903
593	14082
594	13850
595	13865
596	13818
597	13603
598	13815
599	13595
600	13495
601	13685
602	13593
603	13500
604	13570
605	13620
606	13482
607	13068
608	13288
609	13189
610	13388
611	13188
612	12976
613	12936
614	12903
615	12599
616	12658
617	12548
618	12670
619	12624
620	12481
621	12184
622	12495
623	12234
624	12558
625	12289
626	12114
627	11958
628	12196
629	12186
630	12109
631	12117
632	11928
633	11845
634	11913
635	11888
636	11728
637	11753
638	11667
639	11738
640	11416
641	11701
642	11493
643	11690
644	11668
645	11552
646	11492
647	11563
648	11498
649	11474
650	11300
651	11294
652	11243
653	11412
654	11154
655	11241
656	11055
657	10998
658	11244
659	10889
660	10876
661	11009
662	11064
663	10616
664	10852
665	10774
666	10781
667	10574
668	10629
669	10588
670	10792
671	10483
672	10603
673	10745
674	10533
675	10375
676	10435
677	10471
678	10269
679	10369
680	10588
681	10315
682	10355
683	10322
684	10078
685	10123
686	10128
687	10061
688	10069
689	10138
690	10040
691	9956
692	9759
693	9960
694	9960
695	9922
696	9851
697	9727
698	9669
699	9574
700	9818
701	9708
702	9545
703	9496
704	9525
705	9438
706	9529
707	9355
708	9228
709	9286
710	9490
711	9257
712	9189
713	9440
714	9310
715	9220
716	8931
717	9266
718	9218
719	9209
720	8930
721	9246
722	9055
723	9048
724	9027
725	8902
726	8976
727	8933
728	8692
729	8791
730	8574
731	8576
732	8795
733	8838
734	8488
735	8768
736	8600
737	8687
738	8721
739	8621
740	8461
741	8490
742	8537
743	8566
744	8547
745	8533
746	8199
747	8375
748	8466
749	8394
750	8485
751	8321
752	8339
753	8380
754	8201
755	8116
756	8211
757	8154
758	8272
759	8151
760	8100
761	8144
762	8146
763	8086
764	8056
765	8012
766	7919
767	8120
768	8105
769	7958
770	7957
771	8107
772	8004
773	7804
774	7871
775	8018
776	7851
777	7822
778	7736
779	7617
780	7572
781	7690
782	7902
783	7517
784	7604
785	7606
786	7541
787	7521
788	7540
789	7557
790	7426
791	7401
792	7551
793	7409
794	7391
795	7444
796	7253
797	7347
798	7333
799	7356
800	7128
801	7161
802	7198
803	7228
804	7213
805	7269
806	7236
807	7160
808	7170
809	6979
810	7125
811	6986
812	7089
813	7023
814	6922
815	6854
816	6944
817	6875
818	6792
819	6892
820	6885
821	6754
822	6588
823	6797
824	6652
825	6714
826	6596
827	6637
828	6727
829	6787
830	6682
831	6563
832	6670
833	6693
834	6589
835	6666
836	6528
837	6574
838	6452
839	6574
840	6600
841	6532
842	6493
843	6465
844	6477
845	6378
846	6394
847	6285
848	6315
849	6473
850	6331
851	6327
852	6365
853	6395
854	6533
855	6333
856	6280
857	6397
858	6288
859	6292
860	6319
861	6306
862	6189
863	5975
864	6161
865	6088
866	5969
867	6097
868	6145
869	6137
870	6118
871	6027
872	6191
873	6080
874	5929
875	5912
876	6015
877	5963
878	5909
879	5917
880	5884
881	6034
882	5978
883	5966
884	6022
885	5950
886	5884
887	5911
888	5831
889	5876
890	5779
891	5748
892	5735
893	5621
894	5704
895	5805
896	5763
897	5606
898	5637
899	5737
900	5592
901	5522
902	5649
903	5530
904	5501
905	5469
906	5489
907	5515
908	5516
909	5575
910	5476
911	5644
912	5406
913	5507
914	5499
915	5394
916	5473
917	5477
918	5353
919	5545
920	5401
921	5406
922	5364
923	5390
924	5287
925	5290
926	5318
927	5326
928	5313
929	5282
930	5435
931	5335
932	5257
933	5248
934	5119
935	5396
936	5169
937	5176
938	5154
939	5098
940	5133
941	5219
942	5249
943	5176
944	5069
945	5059
946	5150
947	5105
948	5052
949	5107
950	5119
951	5070
952	5155
953	5130
954	5038
955	5072
956	4936
957	5000
958	4985
959	4962
960	5080
961	5058
962	5175
963	5055
964	5138
965	4961
966	4806
967	5087
968	4900
969	4837
970	4970
971	4815
972	4950
973	4835
974	4886
975	4761
976	4839
977	4850
978	4743
979	4721
980	4761
981	4726
982	4759
983	4705
984	4776
985	4686
986	4653
987	4684
988	4782
989	4526
990	4701
991	4832
992	4516
993	4638
994	4577
995	4559
996	4470
997	4539
998	4548
999	4557
1000	75390994