1	4920575322
2	735417590
3	207037069
4	80070265
5	38232607
6	25154524
7	19045852
8	16647107
9	15583795
10	15315840
11	15397253
12	15734992
13	16143533
14	16591697
15	17037798
16	17454971
17	17828094
18	18159107
19	18419453
20	18622051
21	18771447
22	18875811
23	18901052
24	18893576
25	18805735
26	18671562
27	18502872
28	18302060
29	18058347
30	17768823
31	17458239
32	17114589
33	16752810
34	16364113
35	15944426
36	15522503
37	15089538
38	14635042
39	14177738
40	13714332
41	13256193
42	12772088
43	12333159
44	11894997
45	11444069
46	11026855
47	10608933
48	10199084
49	9791979
50	9393928
51	9027402
52	8658939
53	8322034
54	7993122
55	7668132
56	7358172
57	7065620
58	6783972
59	6515419
60	6259359
61	6011451
62	5779551
63	5566879
64	5355757
65	5161850
66	4968503
67	4788450
68	4624230
69	4467628
70	4324682
71	4166182
72	4025988
73	3893759
74	3764058
75	3644591
76	3521935
77	3415102
78	3309032
79	3206174
80	3112472
81	3022257
82	2932744
83	2843898
84	2760990
85	2679481
86	2605489
87	2531437
88	2459991
89	2384917
90	2315713
91	2247105
92	2183984
93	2121655
94	2059810
95	2002437
96	1948680
97	1889349
98	1831480
99	1775175
100	1725499
101	1670527
102	1623554
103	1572853
104	1526119
105	1484336
106	1432595
107	1389795
108	1342844
109	1302778
110	1262426
111	1221818
112	1183369
113	1147436
114	1104855
115	1070530
116	1034877
117	999870
118	966356
119	935561
120	904230
121	872709
122	844356
123	815021
124	786523
125	758243
126	730683
127	706117
128	682205
129	657426
130	634803
131	613639
132	592783
133	572826
134	552445
135	532545
136	513362
137	496297
138	479403
139	462691
140	446466
141	430779
142	416319
143	404173
144	389828
145	377005
146	366138
147	353747
148	341773
149	329426
150	320013
151	309196
152	299772
153	290991
154	281386
155	273318
156	264693
157	257834
158	251245
159	242077
160	233370
161	227905
162	222240
163	216981
164	211302
165	204410
166	198641
167	194757
168	189484
169	185054
170	180218
171	176534
172	172406
173	167459
174	164700
175	160142
176	156684
177	152776
178	149123
179	145778
180	141988
181	139329
182	136730
183	133392
184	130861
185	127528
186	125481
187	123765
188	121476
189	119181
190	116572
191	114342
192	112880
193	110846
194	108008
195	106697
196	104357
197	102685
198	101272
199	99780
200	97939
201	96168
202	95284
203	93247
204	92128
205	90188
206	89392
207	88047
208	87643
209	86129
210	84686
211	83869
212	82433
213	81086
214	79713
215	78406
216	77672
217	76451
218	76057
219	74177
220	73642
221	72330
222	71461
223	70666
224	69516
225	69051
226	68236
227	67222
228	66564
229	65895
230	64863
231	64690
232	63985
233	62976
234	62238
235	62187
236	61052
237	60527
238	60318
239	59500
240	59471
241	58167
242	57488
243	57022
244	56445
245	55766
246	55506
247	55153
248	54183
249	54154
250	53464
251	52558
252	52064
253	52031
254	51266
255	50650
256	49920
257	49582
258	49180
259	49326
260	48391
261	48031
262	48089
263	47218
264	46733
265	46203
266	45927
267	45536
268	44947
269	44860
270	44389
271	44151
272	43709
273	43287
274	42802
275	42636
276	41983
277	41812
278	41376
279	41552
280	40920
281	40273
282	40210
283	39815
284	39312
285	39285
286	38988
287	38749
288	38102
289	38151
290	37505
291	37464
292	36942
293	36903
294	36680
295	36115
296	35923
297	35844
298	35503
299	35494
300	35114
301	34955
302	34833
303	34301
304	34050
305	33547
306	33531
307	33483
308	32778
309	32646
310	32545
311	32315
312	31990
313	31986
314	31560
315	31393
316	31146
317	30790
318	31212
319	30660
320	30409
321	30388
322	30162
323	30004
324	29895
325	29226
326	29463
327	29015
328	28977
329	28447
330	28515
331	28266
332	28492
333	28112
334	27673
335	27536
336	27523
337	26911
338	27513
339	27179
340	26753
341	26644
342	26769
343	26306
344	25908
345	25994
346	25857
347	25600
348	25824
349	25612
350	25625
351	25202
352	25127
353	25131
354	24940
355	24401
356	24659
357	24402
358	24237
359	24017
360	23835
361	23828
362	23838
363	23360
364	23360
365	23268
366	23216
367	22975
368	22434
369	22787
370	22384
371	22151
372	22231
373	22177
374	21933
375	21782
376	21807
377	21487
378	21720
379	21272
380	21489
381	20979
382	20960
383	20856
384	20655
385	20657
386	20496
387	20100
388	20369
389	20436
390	20335
391	20239
392	20069
393	19777
394	19582
395	19883
396	19805
397	19560
398	19588
399	19165
400	19045
401	18928
402	18913
403	19066
404	18593
405	18982
406	18673
407	18827
408	18661
409	18535
410	18668
411	18225
412	18326
413	18363
414	18057
415	18221
416	17983
417	18019
418	17794
419	17867
420	17662
421	17419
422	17444
423	17375
424	17189
425	17158
426	16988
427	17110
428	17052
429	16811
430	16639
431	16533
432	16724
433	16592
434	16854
435	16293
436	16318
437	16171
438	16211
439	16180
440	16125
441	16013
442	16006
443	15792
444	15757
445	15818
446	15520
447	15521
448	15378
449	15471
450	15212
451	15268
452	15312
453	15001
454	15212
455	15270
456	14971
457	15006
458	14853
459	14533
460	14688
461	14715
462	14385
463	14674
464	14428
465	14366
466	14292
467	14152
468	14232
469	13843
470	13794
471	13930
472	13865
473	13707
474	13731
475	13736
476	13621
477	13498
478	13554
479	13629
480	13495
481	13614
482	13268
483	13318
484	13368
485	13297
486	13261
487	13302
488	13140
489	13264
490	12977
491	13074
492	13137
493	12886
494	12863
495	12921
496	12632
497	12633
498	12692
499	12629
500	12569
501	12455
502	12478
503	12367
504	12299
505	12264
506	12124
507	12126
508	12134
509	11976
510	11942
511	11983
512	11863
513	11986
514	12000
515	11691
516	11814
517	11674
518	11596
519	11632
520	11678
521	11391
522	11486
523	11486
524	11329
525	11657
526	11398
527	11225
528	11187
529	11169
530	11139
531	11106
532	11021
533	10980
534	10743
535	10937
536	10911
537	10883
538	10832
539	10791
540	10612
541	10934
542	10790
543	10647
544	10685
545	10414
546	10593
547	10619
548	10401
549	10359
550	10525
551	10301
552	10097
553	10256
554	10304
555	10130
556	10107
557	9932
558	9977
559	10075
560	9975
561	9903
562	10012
563	10056
564	9939
565	9684
566	9731
567	9813
568	9508
569	9505
570	9725
571	9591
572	9818
573	9514
574	9636
575	9676
576	9651
577	9459
578	9497
579	9405
580	9455
581	9409
582	9644
583	9317
584	9342
585	9189
586	9162
587	9069
588	9195
589	9255
590	9073
591	9316
592	8945
593	8891
594	9246
595	8919
596	9098
597	8902
598	8978
599	9023
600	8925
601	8747
602	8814
603	8797
604	8804
605	8755
606	8694
607	8754
608	8691
609	8519
610	8568
611	8495
612	8533
613	8471
614	8540
615	8351
616	8447
617	8508
618	8220
619	8283
620	8308
621	8315
622	8440
623	8345
624	8237
625	8229
626	8101
627	8168
628	8072
629	8239
630	8067
631	8107
632	8100
633	7967
634	7966
635	7955
636	7871
637	7820
638	7807
639	7847
640	7763
641	7734
642	8018
643	7718
644	7689
645	7681
646	7879
647	7806
648	7810
649	7765
650	7691
651	7733
652	7708
653	7695
654	7529
655	7616
656	7655
657	7458
658	7552
659	7472
660	7428
661	7392
662	7364
663	7295
664	7319
665	7398
666	7276
667	7257
668	7168
669	7178
670	7174
671	7134
672	6916
673	7174
674	7038
675	6953
676	7166
677	6972
678	7139
679	7146
680	7030
681	6860
682	7039
683	6793
684	6815
685	6892
686	6855
687	6869
688	6785
689	6620
690	6638
691	6676
692	6783
693	6614
694	6602
695	6639
696	6684
697	6622
698	6574
699	6484
700	6346
701	6311
702	6379
703	6421
704	6419
705	6413
706	6455
707	6264
708	6373
709	6391
710	6328
711	6384
712	6316
713	6424
714	6405
715	6283
716	6284
717	6263
718	6294
719	6133
720	6233
721	6253
722	6062
723	6223
724	6197
725	6176
726	6203
727	6263
728	6145
729	6185
730	6090
731	6169
732	6126
733	6060
734	6111
735	5912
736	5846
737	5990
738	6013
739	5890
740	5870
741	5937
742	5919
743	5949
744	5756
745	5738
746	5836
747	5775
748	5817
749	5789
750	5639
751	5715
752	5741
753	5649
754	5860
755	5712
756	5746
757	5622
758	5588
759	5579
760	5590
761	5660
762	5543
763	5628
764	5696
765	5402
766	5562
767	5627
768	5433
769	5335
770	5422
771	5441
772	5303
773	5341
774	5454
775	5468
776	5374
777	5492
778	5373
779	5267
780	5309
781	5344
782	5313
783	5312
784	5246
785	5284
786	5337
787	5170
788	5225
789	5242
790	5170
791	5248
792	5195
793	5052
794	5115
795	5154
796	5085
797	5202
798	5212
799	5029
800	5041
801	5048
802	5031
803	5061
804	4952
805	4849
806	5014
807	4951
808	4890
809	4861
810	4766
811	4892
812	4806
813	4876
814	4886
815	4952
816	4885
817	4841
818	4791
819	4834
820	4717
821	4726
822	4806
823	4868
824	4832
825	4701
826	4803
827	4695
828	4713
829	4768
830	4744
831	4664
832	4594
833	4836
834	4717
835	4655
836	4644
837	4514
838	4704
839	4549
840	4679
841	4486
842	4565
843	4653
844	4562
845	4616
846	4547
847	4614
848	4610
849	4475
850	4542
851	4598
852	4415
853	4524
854	4500
855	4311
856	4511
857	4468
858	4374
859	4462
860	4468
861	4368
862	4472
863	4369
864	4307
865	4278
866	4315
867	4384
868	4397
869	4297
870	4391
871	4240
872	4255
873	4252
874	4322
875	4288
876	4279
877	4357
878	4254
879	4245
880	4218
881	4116
882	4218
883	4128
884	4177
885	4155
886	4275
887	4181
888	4177
889	4090
890	4120
891	4217
892	4096
893	4137
894	4069
895	4192
896	4118
897	3998
898	4130
899	4150
900	3968
901	4123
902	4078
903	4117
904	3957
905	4057
906	4018
907	3970
908	4048
909	4057
910	4027
911	3956
912	4025
913	4006
914	3879
915	3963
916	3942
917	3965
918	3908
919	3987
920	3899
921	3898
922	3859
923	3973
924	3902
925	3825
926	3869
927	3752
928	3784
929	3640
930	3704
931	3757
932	3807
933	3762
934	3796
935	3732
936	3784
937	3778
938	3640
939	3611
940	3830
941	3770
942	3641
943	3664
944	3683
945	3582
946	3619
947	3691
948	3656
949	3648
950	3645
951	3549
952	3608
953	3681
954	3529
955	3556
956	3581
957	3656
958	3639
959	3614
960	3603
961	3677
962	3603
963	3587
964	3636
965	3605
966	3491
967	3500
968	3477
969	3516
970	3621
971	3572
972	3536
973	3570
974	3460
975	3460
976	3477
977	3468
978	3389
979	3444
980	3473
981	3398
982	3507
983	3453
984	3399
985	3403
986	3334
987	3414
988	3394
989	3442
990	3423
991	3417
992	3349
993	3459
994	3404
995	3378
996	3295
997	3365
998	3384
999	3321
1000	14031998