1	5832814943
2	584423158
3	196415777
4	108296592
5	83390004
6	79150476
7	79425289
8	80677609
9	81290213
10	80811326
11	79168560
12	76616711
13	73205399
14	69298835
15	65028827
16	60588512
17	56219664
18	51896409
19	47764229
20	43816252
21	40172720
22	36783161
23	33662900
24	30827601
25	28222211
26	25845955
27	23723259
28	21755283
29	19972588
30	18345790
31	16878051
32	15534581
33	14279379
34	13161657
35	12132739
36	11170639
37	10300466
38	9500518
39	8762966
40	8098549
41	7476274
42	6893313
43	6362759
44	5875544
45	5432032
46	5023158
47	4651063
48	4309261
49	3992286
50	3699936
51	3438486
52	3196984
53	2981295
54	2782575
55	2598021
56	2429128
57	2279578
58	2137745
59	2005720
60	1884253
61	1778877
62	1680021
63	1591064
64	1509818
65	1431227
66	1361537
67	1296793
68	1242189
69	1186612
70	1134431
71	1084000
72	1044266
73	1003451
74	963291
75	931735
76	898347
77	864838
78	835218
79	807006
80	782661
81	758223
82	733476
83	713263
84	693927
85	672430
86	654385
87	635569
88	618396
89	602396
90	584845
91	572094
92	556644
93	544780
94	529863
95	517675
96	504854
97	493680
98	482820
99	471528
100	460771
101	448990
102	441922
103	432120
104	423692
105	413782
106	405703
107	398260
108	390490
109	382579
110	374656
111	367533
112	360949
113	354326
114	346928
115	341858
116	334290
117	330755
118	325179
119	318630
120	311576
121	307343
122	301393
123	297641
124	292900
125	287832
126	282278
127	278559
128	273531
129	268831
130	264570
131	259606
132	256010
133	251611
134	249373
135	244721
136	240925
137	238654
138	233917
139	230273
140	227147
141	223554
142	220476
143	217389
144	214849
145	212509
146	208645
147	205954
148	202730
149	200220
150	197907
151	194869
152	191458
153	189761
154	187094
155	185231
156	182284
157	179515
158	176769
159	174770
160	172797
161	171192
162	167912
163	166268
164	163692
165	161761
166	160587
167	158408
168	156220
169	154457
170	153138
171	149790
172	148957
173	147195
174	145080
175	143564
176	141977
177	140763
178	139393
179	137624
180	135656
181	133583
182	132727
183	132010
184	129762
185	128609
186	126474
187	125606
188	124912
189	122074
190	121924
191	120250
192	118396
193	117682
194	117032
195	115822
196	114356
197	113028
198	111685
199	110289
200	109837
201	109268
202	108145
203	107277
204	106066
205	104067
206	103745
207	102350
208	102065
209	100577
210	99401
211	98482
212	97752
213	97195
214	95960
215	94768
216	94242
217	93359
218	93080
219	91427
220	90357
221	90485
222	89142
223	88356
224	87549
225	86617
226	85703
227	85116
228	84610
229	83507
230	82882
231	81365
232	82227
233	80423
234	80114
235	79592
236	79200
237	78305
238	77239
239	76937
240	76430
241	75132
242	75005
243	74017
244	72983
245	72601
246	72213
247	71317
248	70557
249	70531
250	70066
251	68764
252	68492
253	68067
254	67823
255	67246
256	66944
257	66114
258	65735
259	64532
260	64668
261	63265
262	63470
263	63343
264	62472
265	62364
266	61879
267	61098
268	60981
269	60135
270	59382
271	59411
272	58912
273	58552
274	58195
275	57460
276	57053
277	56906
278	56257
279	55840
280	55316
281	55139
282	54913
283	54626
284	53997
285	53883
286	53581
287	52965
288	53036
289	52278
290	52456
291	51322
292	51068
293	51220
294	50424
295	49874
296	49483
297	49762
298	48726
299	48852
300	48276
301	47532
302	47232
303	47284
304	47073
305	46837
306	46146
307	46015
308	45479
309	45217
310	45308
311	44961
312	44542
313	44251
314	44033
315	43917
316	43589
317	43203
318	42727
319	42666
320	42157
321	42292
322	41678
323	41605
324	41407
325	41297
326	40667
327	40578
328	40121
329	40283
330	39850
331	39566
332	39522
333	39569
334	38931
335	38561
336	38734
337	38115
338	37946
339	37927
340	37414
341	37621
342	37208
343	37093
344	36518
345	36912
346	36364
347	35969
348	35520
349	35595
350	35310
351	35142
352	34996
353	34476
354	34708
355	34080
356	34079
357	33781
358	33978
359	33751
360	33313
361	33387
362	33433
363	32927
364	33032
365	32549
366	32342
367	32350
368	32200
369	31846
370	31786
371	31275
372	31242
373	31456
374	31113
375	30674
376	30539
377	30378
378	30352
379	30409
380	30098
381	30212
382	29821
383	29368
384	29488
385	29368
386	29379
387	29121
388	28779
389	29037
390	28737
391	28355
392	28238
393	28051
394	28064
395	27758
396	27828
397	27665
398	27454
399	27296
400	27090
401	27194
402	26918
403	26847
404	26752
405	26507
406	26401
407	26253
408	26109
409	26274
410	25954
411	25851
412	25837
413	25596
414	25359
415	25162
416	25397
417	25168
418	24955
419	24722
420	24681
421	24353
422	24273
423	24427
424	24385
425	24145
426	23885
427	23715
428	23529
429	23749
430	23465
431	23531
432	23236
433	23287
434	23229
435	23002
436	23265
437	22856
438	22666
439	22683
440	22230
441	22671
442	22400
443	22236
444	22165
445	21947
446	21912
447	21661
448	21730
449	21466
450	21300
451	21468
452	21182
453	21266
454	21078
455	21022
456	20896
457	20620
458	20846
459	20474
460	20297
461	20753
462	20201
463	20249
464	20145
465	20246
466	20092
467	19702
468	19657
469	19889
470	19564
471	19764
472	19228
473	19452
474	19244
475	19034
476	19233
477	19040
478	19051
479	18947
480	18833
481	18825
482	18510
483	18575
484	18369
485	18352
486	18315
487	18181
488	18285
489	18114
490	18171
491	18136
492	17688
493	17914
494	17813
495	17547
496	17543
497	17581
498	17395
499	17418
500	17341
501	17040
502	17159
503	17178
504	17141
505	17173
506	16823
507	17179
508	17017
509	16805
510	16805
511	16534
512	16901
513	16635
514	16563
515	16399
516	16378
517	16232
518	16299
519	16259
520	15950
521	16022
522	15793
523	15762
524	15972
525	15529
526	15972
527	15458
528	15362
529	15585
530	15491
531	15592
532	15271
533	15069
534	15071
535	15040
536	15058
537	15119
538	14917
539	14891
540	15040
541	14660
542	14698
543	14562
544	14485
545	14470
546	14475
547	14527
548	14503
549	14263
550	14184
551	14086
552	14258
553	14239
554	14305
555	14067
556	14204
557	13951
558	13875
559	13943
560	13713
561	13659
562	13573
563	13729
564	13585
565	13705
566	13523
567	13467
568	13590
569	13182
570	13199
571	13255
572	13241
573	13098
574	13128
575	12961
576	12989
577	12811
578	13064
579	12954
580	12865
581	12978
582	12867
583	12704
584	12450
585	12726
586	12336
587	12253
588	12482
589	12349
590	12317
591	12366
592	12419
593	12366
594	12044
595	12098
596	12093
597	12196
598	12159
599	12075
600	11961
601	12023
602	11978
603	12003
604	11950
605	11882
606	11692
607	11660
608	11850
609	11793
610	11520
611	11640
612	11578
613	11611
614	11635
615	11298
616	11333
617	11394
618	11258
619	11487
620	11265
621	11299
622	11112
623	11200
624	11368
625	11069
626	10953
627	10973
628	11067
629	11153
630	10903
631	10832
632	10720
633	10783
634	10711
635	10538
636	10726
637	10747
638	10582
639	10603
640	10641
641	10817
642	10622
643	10479
644	10683
645	10467
646	10567
647	10196
648	10429
649	10314
650	10474
651	10309
652	10265
653	10398
654	10175
655	10075
656	10165
657	10199
658	10142
659	9982
660	9994
661	9886
662	9986
663	9883
664	9928
665	9780
666	9685
667	9766
668	9733
669	9892
670	9685
671	9760
672	9574
673	9625
674	9852
675	9580
676	9566
677	9480
678	9573
679	9445
680	9369
681	9277
682	9471
683	9272
684	9283
685	9231
686	9280
687	9031
688	9131
689	9021
690	9058
691	9065
692	9102
693	9005
694	9012
695	9136
696	8942
697	9006
698	8894
699	8916
700	8868
701	8893
702	8969
703	9007
704	8722
705	8765
706	8665
707	8751
708	8574
709	8694
710	8475
711	8779
712	8510
713	8729
714	8432
715	8473
716	8340
717	8360
718	8278
719	8302
720	8444
721	8253
722	8240
723	8120
724	8259
725	8205
726	8242
727	8107
728	8123
729	8278
730	8071
731	8075
732	8050
733	8072
734	8098
735	8108
736	8083
737	8224
738	7988
739	7941
740	8095
741	7896
742	7915
743	7887
744	7796
745	7884
746	7922
747	7930
748	7712
749	7711
750	7688
751	7705
752	7727
753	7595
754	7694
755	7505
756	7704
757	7414
758	7552
759	7380
760	7503
761	7375
762	7508
763	7263
764	7377
765	7441
766	7423
767	7358
768	7452
769	7275
770	7387
771	7296
772	7330
773	7281
774	7189
775	7130
776	7244
777	7117
778	7104
779	7086
780	7030
781	7114
782	7014
783	6835
784	7023
785	6972
786	6915
787	6942
788	6880
789	6936
790	6927
791	6995
792	7039
793	6882
794	6890
795	6913
796	6818
797	6799
798	6864
799	6669
800	6689
801	6871
802	6880
803	6838
804	6666
805	6699
806	6664
807	6666
808	6576
809	6424
810	6635
811	6565
812	6385
813	6484
814	6466
815	6525
816	6394
817	6591
818	6388
819	6405
820	6401
821	6328
822	6366
823	6514
824	6502
825	6300
826	6399
827	6325
828	6243
829	6271
830	6331
831	6350
832	6218
833	6257
834	6376
835	6200
836	6204
837	6136
838	6161
839	6194
840	6108
841	6159
842	5989
843	6095
844	5961
845	6142
846	6052
847	6105
848	5971
849	5945
850	6004
851	5935
852	5976
853	5887
854	5812
855	5924
856	6048
857	5723
858	5818
859	5688
860	5777
861	5835
862	5778
863	5762
864	5684
865	5703
866	5694
867	5777
868	5693
869	5759
870	5694
871	5732
872	5787
873	5628
874	5632
875	5706
876	5705
877	5650
878	5501
879	5721
880	5671
881	5555
882	5426
883	5645
884	5508
885	5463
886	5396
887	5536
888	5473
889	5516
890	5408
891	5493
892	5400
893	5392
894	5441
895	5378
896	5470
897	5364
898	5441
899	5377
900	5293
901	5323
902	5223
903	5280
904	5273
905	5318
906	5172
907	5189
908	5241
909	5222
910	5176
911	5223
912	5143
913	5114
914	5169
915	5193
916	5127
917	5158
918	5166
919	5119
920	5234
921	5009
922	5098
923	5036
924	5073
925	5059
926	5018
927	5059
928	4982
929	5004
930	5067
931	5111
932	5169
933	4895
934	4938
935	4801
936	4947
937	5012
938	4908
939	4862
940	4987
941	4792
942	4924
943	5042
944	4965
945	4902
946	4867
947	4859
948	4783
949	4805
950	4795
951	4851
952	4837
953	4815
954	4811
955	4746
956	4681
957	4680
958	4730
959	4738
960	4605
961	4823
962	4674
963	4667
964	4693
965	4702
966	4592
967	4693
968	4635
969	4644
970	4649
971	4648
972	4687
973	4650
974	4566
975	4643
976	4644
977	4553
978	4681
979	4512
980	4535
981	4601
982	4515
983	4497
984	4530
985	4519
986	4431
987	4380
988	4490
989	4338
990	4378
991	4411
992	4415
993	4343
994	4305
995	4396
996	4373
997	4240
998	4298
999	4357
1000	35071555