1	7240698498
2	546013739
3	75360595
4	49729573
5	25252968
6	26224671
7	26273974
8	29471197
9	33105845
10	37344826
11	41750243
12	46222297
13	50474054
14	54315108
15	57620885
16	60292617
17	62266669
18	63546057
19	64137276
20	64067242
21	63445284
22	62323848
23	60799871
24	58995587
25	56893886
26	54688604
27	52381404
28	50030437
29	47690710
30	45395795
31	43192445
32	41015303
33	38971498
34	37015319
35	35164814
36	33422682
37	31791986
38	30225399
39	28781824
40	27387638
41	26071970
42	24849338
43	23688400
44	22595682
45	21561928
46	20591793
47	19651231
48	18773005
49	17932345
50	17119615
51	16359321
52	15634243
53	14944629
54	14301241
55	13680335
56	13096481
57	12530850
58	11983128
59	11467329
60	10990515
61	10518468
62	10086111
63	9659164
64	9250746
65	8870549
66	8510775
67	8157921
68	7823004
69	7500264
70	7202883
71	6923886
72	6657159
73	6394547
74	6139319
75	5907350
76	5686006
77	5476781
78	5261285
79	5067233
80	4875001
81	4702098
82	4533312
83	4361061
84	4208865
85	4058083
86	3909111
87	3774500
88	3636336
89	3508347
90	3384070
91	3265336
92	3154064
93	3040633
94	2936218
95	2839534
96	2745604
97	2654131
98	2568429
99	2482990
100	2400070
101	2320664
102	2248345
103	2173418
104	2103775
105	2033223
106	1968370
107	1905485
108	1844873
109	1783681
110	1725926
111	1668361
112	1619348
113	1567375
114	1518742
115	1473783
116	1426039
117	1386738
118	1341896
119	1299831
120	1259085
121	1223142
122	1185023
123	1149395
124	1111862
125	1080772
126	1045567
127	1013966
128	985697
129	954891
130	924795
131	898238
132	872793
133	847673
134	822415
135	799838
136	778265
137	755866
138	733139
139	714237
140	693405
141	673395
142	653491
143	634620
144	617436
145	600638
146	582908
147	567574
148	551081
149	536836
150	520921
151	504888
152	492049
153	477953
154	465310
155	453748
156	440947
157	428788
158	415478
159	404582
160	394541
161	383339
162	373364
163	363779
164	354708
165	344017
166	336263
167	327251
168	319620
169	310719
170	302921
171	294143
172	286944
173	279243
174	272350
175	265069
176	258120
177	251610
178	246016
179	239650
180	233273
181	228349
182	222992
183	218256
184	212852
185	207356
186	203519
187	198514
188	193129
189	189408
190	184801
191	179027
192	175366
193	171312
194	168040
195	163724
196	159544
197	155520
198	152206
199	148903
200	145673
201	143031
202	139375
203	136286
204	133485
205	129367
206	127689
207	123668
208	121815
209	118329
210	116177
211	113527
212	111386
213	109069
214	106803
215	104482
216	103066
217	100495
218	98242
219	96966
220	94267
221	92563
222	90909
223	89201
224	86401
225	85425
226	83669
227	82133
228	80859
229	79546
230	78037
231	76020
232	74806
233	74080
234	72273
235	70952
236	70230
237	68383
238	67144
239	65928
240	65030
241	64382
242	62559
243	61230
244	60772
245	59486
246	59061
247	57837
248	56729
249	55710
250	54853
251	53899
252	53187
253	52031
254	51398
255	50565
256	50127
257	48468
258	48052
259	47008
260	46464
261	45788
262	45230
263	44596
264	44246
265	42981
266	42805
267	42157
268	41600
269	40976
270	40352
271	39655
272	39500
273	39051
274	38459
275	37740
276	37279
277	36621
278	36436
279	35559
280	35134
281	34930
282	34342
283	33673
284	33607
285	33062
286	32802
287	32387
288	31982
289	31734
290	31527
291	30994
292	30613
293	30184
294	29749
295	29748
296	29072
297	28969
298	28457
299	28058
300	27876
301	27751
302	27202
303	27082
304	26665
305	26458
306	26328
307	25916
308	25476
309	25244
310	25127
311	25103
312	24697
313	24509
314	24101
315	24215
316	23521
317	23482
318	23373
319	22683
320	22715
321	22463
322	22316
323	22189
324	21681
325	21635
326	21345
327	21132
328	21066
329	20649
330	20784
331	20250
332	20298
333	20236
334	20204
335	20019
336	19599
337	19406
338	19366
339	19325
340	19018
341	19012
342	18826
343	18464
344	18276
345	18218
346	18248
347	17866
348	17867
349	17421
350	17764
351	17606
352	17353
353	17365
354	17182
355	16893
356	16850
357	16632
358	16547
359	16712
360	16193
361	15980
362	15961
363	15911
364	15625
365	15573
366	15553
367	15569
368	15374
369	15201
370	15239
371	15353
372	15187
373	15185
374	14648
375	14977
376	14547
377	14469
378	14315
379	14321
380	14477
381	14001
382	14056
383	14017
384	13815
385	13730
386	13627
387	13597
388	13319
389	13459
390	13189
391	13122
392	12844
393	12872
394	12949
395	12728
396	12360
397	12460
398	12476
399	12290
400	12459
401	12134
402	12142
403	12168
404	12082
405	11891
406	11949
407	11760
408	11747
409	11776
410	11573
411	11580
412	11602
413	11546
414	11455
415	11422
416	11580
417	11256
418	11426
419	11291
420	11243
421	11122
422	10980
423	11078
424	11043
425	10949
426	10632
427	10691
428	10633
429	10619
430	10549
431	10501
432	10363
433	10242
434	10213
435	10279
436	10128
437	9931
438	10036
439	9900
440	9724
441	9812
442	9615
443	9639
444	9486
445	9408
446	9424
447	9440
448	9303
449	9093
450	9306
451	8966
452	9151
453	8887
454	8856
455	8847
456	8897
457	8760
458	8747
459	8683
460	8582
461	8736
462	8386
463	8509
464	8630
465	8458
466	8336
467	8558
468	8264
469	8270
470	8391
471	8327
472	8133
473	8042
474	8132
475	7956
476	7960
477	7882
478	7883
479	7918
480	7793
481	7895
482	7754
483	7905
484	7684
485	7668
486	7666
487	7515
488	7452
489	7542
490	7423
491	7501
492	7299
493	7303
494	7327
495	7325
496	7123
497	7193
498	7242
499	7061
500	7128
501	6935
502	7004
503	6860
504	6897
505	6794
506	6813
507	6796
508	6656
509	6779
510	6584
511	6582
512	6694
513	6635
514	6573
515	6589
516	6491
517	6527
518	6471
519	6429
520	6317
521	6434
522	6260
523	6193
524	6243
525	6100
526	6210
527	6282
528	6256
529	6067
530	6216
531	6207
532	6071
533	6153
534	6114
535	6037
536	5819
537	5856
538	5943
539	5882
540	5839
541	5798
542	5736
543	5819
544	5821
545	5819
546	5774
547	5752
548	5564
549	5535
550	5619
551	5614
552	5482
553	5359
554	5486
555	5451
556	5482
557	5473
558	5309
559	5366
560	5287
561	5390
562	5171
563	5126
564	5202
565	5244
566	5153
567	5130
568	5133
569	5163
570	5121
571	5123
572	4984
573	4860
574	4891
575	5014
576	4922
577	4830
578	4912
579	4938
580	4798
581	4851
582	4755
583	4844
584	4716
585	4681
586	4772
587	4763
588	4768
589	4611
590	4625
591	4724
592	4546
593	4704
594	4561
595	4606
596	4519
597	4575
598	4561
599	4485
600	4466
601	4477
602	4413
603	4486
604	4418
605	4338
606	4334
607	4366
608	4265
609	4334
610	4281
611	4307
612	4209
613	4291
614	4204
615	4147
616	4409
617	4132
618	4174
619	4184
620	4162
621	4056
622	4053
623	4012
624	4066
625	4057
626	4086
627	4057
628	3929
629	3956
630	3777
631	3927
632	3872
633	3958
634	3951
635	3933
636	3826
637	3930
638	3875
639	3936
640	3783
641	3905
642	3857
643	3820
644	3825
645	3728
646	3770
647	3799
648	3800
649	3697
650	3636
651	3739
652	3757
653	3695
654	3593
655	3608
656	3619
657	3661
658	3729
659	3647
660	3581
661	3657
662	3465
663	3521
664	3515
665	3445
666	3546
667	3523
668	3412
669	3431
670	3373
671	3453
672	3425
673	3506
674	3368
675	3412
676	3393
677	3474
678	3403
679	3421
680	3348
681	3355
682	3397
683	3357
684	3386
685	3390
686	3321
687	3298
688	3357
689	3280
690	3272
691	3293
692	3325
693	3249
694	3151
695	3216
696	3285
697	3085
698	3097
699	3134
700	3171
701	3172
702	3155
703	3122
704	3052
705	3178
706	3116
707	3157
708	3044
709	3118
710	3040
711	2972
712	3012
713	3029
714	3018
715	2994
716	3062
717	2970
718	2953
719	2899
720	2972
721	3010
722	2965
723	2952
724	2876
725	2913
726	2888
727	2861
728	2975
729	2815
730	2913
731	2868
732	3036
733	2847
734	2859
735	2871
736	2927
737	2864
738	2770
739	2747
740	2861
741	2758
742	2803
743	2802
744	2754
745	2877
746	2739
747	2831
748	2747
749	2690
750	2736
751	2697
752	2641
753	2726
754	2687
755	2685
756	2714
757	2578
758	2659
759	2609
760	2669
761	2622
762	2672
763	2622
764	2663
765	2540
766	2597
767	2714
768	2556
769	2511
770	2512
771	2649
772	2622
773	2550
774	2642
775	2603
776	2614
777	2582
778	2484
779	2508
780	2597
781	2465
782	2585
783	2522
784	2540
785	2454
786	2497
787	2510
788	2471
789	2488
790	2486
791	2396
792	2488
793	2489
794	2438
795	2432
796	2402
797	2449
798	2421
799	2408
800	2378
801	2478
802	2402
803	2291
804	2263
805	2381
806	2348
807	2291
808	2342
809	2336
810	2409
811	2256
812	2366
813	2296
814	2306
815	2216
816	2253
817	2263
818	2337
819	2250
820	2346
821	2192
822	2185
823	2332
824	2281
825	2247
826	2272
827	2246
828	2230
829	2284
830	2302
831	2266
832	2118
833	2189
834	2170
835	2220
836	2188
837	2167
838	2194
839	2190
840	2108
841	2134
842	2094
843	2191
844	2151
845	2149
846	2134
847	2112
848	2112
849	2175
850	2038
851	2116
852	2109
853	2143
854	2077
855	2016
856	2125
857	2037
858	2119
859	2068
860	2038
861	2095
862	2013
863	2069
864	2050
865	2023
866	2065
867	2063
868	2024
869	2035
870	1995
871	2084
872	2059
873	2071
874	2082
875	2015
876	1949
877	1995
878	1986
879	2020
880	1980
881	1969
882	2003
883	1918
884	1940
885	1920
886	1898
887	1892
888	1953
889	1832
890	1885
891	1909
892	1879
893	1885
894	1939
895	1893
896	1944
897	1840
898	1785
899	1904
900	1837
901	1848
902	1972
903	1878
904	1869
905	1866
906	1807
907	1843
908	1799
909	1816
910	1798
911	1783
912	1847
913	1900
914	1801
915	1759
916	1774
917	1837
918	1783
919	1774
920	1809
921	1686
922	1671
923	1755
924	1844
925	1708
926	1803
927	1756
928	1774
929	1745
930	1672
931	1794
932	1756
933	1746
934	1628
935	1716
936	1801
937	1693
938	1723
939	1670
940	1722
941	1752
942	1697
943	1750
944	1735
945	1684
946	1659
947	1757
948	1736
949	1660
950	1643
951	1667
952	1612
953	1604
954	1668
955	1689
956	1701
957	1683
958	1653
959	1603
960	1669
961	1638
962	1649
963	1679
964	1541
965	1586
966	1619
967	1556
968	1622
969	1538
970	1527
971	1581
972	1635
973	1505
974	1574
975	1636
976	1551
977	1543
978	1579
979	1554
980	1576
981	1533
982	1620
983	1517
984	1614
985	1638
986	1470
987	1571
988	1573
989	1578
990	1580
991	1483
992	1544
993	1569
994	1605
995	1512
996	1486
997	1602
998	1535
999	1495
1000	12447889