1	9030060450
2	943757307
3	233511375
4	103937588
5	56425789
6	39817412
7	30240415
8	25297381
9	22193413
10	20297421
11	19038923
12	18206163
13	17621395
14	17197617
15	16878190
16	16631392
17	16406073
18	16240649
19	16095743
20	15920328
21	15760232
22	15621100
23	15450433
24	15261302
25	15086329
26	14907887
27	14712913
28	14522714
29	14319785
30	14093362
31	13887247
32	13651691
33	13431548
34	13205732
35	12982102
36	12731570
37	12494311
38	12258024
39	12015261
40	11767651
41	11525602
42	11290785
43	11051444
44	10803121
45	10562910
46	10329157
47	10086393
48	9847832
49	9616332
50	9397127
51	9170705
52	8948888
53	8734765
54	8514911
55	8306496
56	8089575
57	7895558
58	7699762
59	7505028
60	7316857
61	7140929
62	6965335
63	6784274
64	6619734
65	6450668
66	6300114
67	6151221
68	5996663
69	5846146
70	5712389
71	5566252
72	5439607
73	5308661
74	5177923
75	5058549
76	4933924
77	4816330
78	4701685
79	4593488
80	4484206
81	4376478
82	4272611
83	4170019
84	4067314
85	3968550
86	3868553
87	3772462
88	3677611
89	3585290
90	3493141
91	3403406
92	3317457
93	3231145
94	3144176
95	3063124
96	2980784
97	2902352
98	2823521
99	2746064
100	2671709
101	2596313
102	2524185
103	2453810
104	2383900
105	2313555
106	2245400
107	2181052
108	2114921
109	2052788
110	1994191
111	1935066
112	1879974
113	1821348
114	1766468
115	1713460
116	1662270
117	1610828
118	1560788
119	1514195
120	1467607
121	1422130
122	1381383
123	1337060
124	1297239
125	1257048
126	1217823
127	1180180
128	1143712
129	1107773
130	1075065
131	1044659
132	1014706
133	986109
134	959132
135	931109
136	905370
137	880448
138	855475
139	832122
140	809361
141	786657
142	766855
143	746372
144	726429
145	708144
146	689551
147	669286
148	655357
149	640161
150	622657
151	610535
152	595268
153	580586
154	567631
155	554950
156	542458
157	531232
158	519948
159	510463
160	498366
161	488155
162	479067
163	467976
164	459921
165	449978
166	440815
167	432518
168	424764
169	417486
170	408543
171	401510
172	395263
173	386419
174	379408
175	374784
176	369142
177	363015
178	356149
179	349804
180	345519
181	339278
182	334039
183	328851
184	323283
185	317930
186	313725
187	309031
188	303610
189	300019
190	294313
191	289727
192	286202
193	282977
194	278896
195	273858
196	271331
197	267794
198	264450
199	261394
200	257345
201	254636
202	251676
203	247744
204	244519
205	240883
206	237616
207	233579
208	230303
209	229210
210	226512
211	223313
212	221285
213	218904
214	216198
215	213692
216	210857
217	207948
218	205540
219	202956
220	200935
221	197378
222	195920
223	193577
224	192380
225	189376
226	187974
227	186007
228	184251
229	182325
230	179183
231	177848
232	176531
233	174627
234	172532
235	170674
236	167908
237	166725
238	165782
239	163486
240	162251
241	159894
242	158349
243	156348
244	156029
245	153797
246	152084
247	151007
248	149511
249	148000
250	145462
251	145273
252	144312
253	142983
254	141504
255	140485
256	138525
257	136920
258	136401
259	134644
260	133545
261	132571
262	131135
263	129656
264	128410
265	127649
266	126108
267	125558
268	124236
269	123271
270	122368
271	121256
272	120603
273	119054
274	117349
275	116629
276	116475
277	115205
278	114304
279	113298
280	112191
281	110745
282	109956
283	109991
284	108440
285	107761
286	106301
287	105722
288	104223
289	103981
290	102493
291	102209
292	100870
293	100129
294	99788
295	98645
296	98166
297	97692
298	97070
299	95820
300	95078
301	94927
302	94212
303	92912
304	91897
305	91279
306	91122
307	90816
308	89454
309	89339
310	88508
311	87879
312	87542
313	87356
314	86100
315	85338
316	85443
317	84529
318	83910
319	83068
320	82799
321	82153
322	80961
323	80968
324	80397
325	79569
326	78985
327	79109
328	78082
329	78159
330	77168
331	76854
332	75805
333	75221
334	74764
335	74386
336	73828
337	73423
338	72904
339	72385
340	72296
341	71662
342	70890
343	70734
344	70510
345	69752
346	69106
347	69123
348	68329
349	68169
350	67980
351	67885
352	66760
353	66252
354	66382
355	65696
356	65584
357	64611
358	64519
359	64119
360	63851
361	63483
362	62559
363	62680
364	62104
365	61793
366	61417
367	61116
368	60835
369	60048
370	60038
371	59343
372	59280
373	59224
374	58659
375	58432
376	57374
377	57654
378	57104
379	56919
380	56679
381	56209
382	55967
383	55875
384	54927
385	54982
386	54469
387	54557
388	54168
389	53852
390	53395
391	52585
392	52990
393	52724
394	52032
395	51995
396	51866
397	51055
398	50766
399	50448
400	50304
401	50260
402	50142
403	49214
404	49413
405	48963
406	48863
407	48493
408	48264
409	48112
410	48258
411	47686
412	47263
413	47409
414	46740
415	46849
416	46662
417	46430
418	46392
419	45624
420	44794
421	45102
422	44495
423	44338
424	44291
425	44386
426	43734
427	43190
428	43439
429	43198
430	42855
431	43158
432	42719
433	42116
434	42369
435	42095
436	41915
437	41808
438	41396
439	41718
440	41119
441	40931
442	40897
443	40935
444	40638
445	40269
446	39992
447	40177
448	39692
449	39916
450	39328
451	39504
452	39061
453	39121
454	38538
455	38645
456	38703
457	38265
458	37814
459	38001
460	37720
461	37524
462	37085
463	37197
464	36673
465	36923
466	36468
467	36449
468	36265
469	36226
470	36064
471	35810
472	35812
473	35947
474	35285
475	34809
476	35303
477	35154
478	34714
479	34743
480	34407
481	34238
482	33967
483	33884
484	33622
485	33441
486	33418
487	33290
488	33496
489	33259
490	33304
491	33126
492	33023
493	32351
494	32616
495	32610
496	32418
497	32349
498	31986
499	31455
500	31768
501	31636
502	31826
503	31271
504	31212
505	31169
506	31124
507	30567
508	30731
509	30579
510	30093
511	30160
512	30404
513	29783
514	29608
515	30012
516	29780
517	29747
518	29544
519	29460
520	29046
521	29317
522	29376
523	28861
524	29137
525	28717
526	28737
527	28479
528	28617
529	28585
530	28135
531	28136
532	28110
533	27780
534	27822
535	27668
536	27559
537	27400
538	27140
539	27159
540	26909
541	26926
542	26886
543	26766
544	26980
545	26603
546	26469
547	26366
548	26491
549	25972
550	25834
551	25889
552	25872
553	25651
554	25687
555	25455
556	25546
557	25064
558	25059
559	25401
560	25020
561	25289
562	24820
563	24940
564	24961
565	24698
566	24481
567	24455
568	24497
569	24314
570	24307
571	24130
572	24301
573	23893
574	23734
575	23724
576	23729
577	23693
578	23262
579	23376
580	23228
581	23198
582	23099
583	22741
584	22936
585	22739
586	22823
587	22798
588	22791
589	22592
590	22480
591	22777
592	22441
593	22177
594	22467
595	22258
596	22150
597	22316
598	21941
599	22193
600	21784
601	21800
602	21992
603	21897
604	21720
605	21880
606	21742
607	21598
608	21514
609	21259
610	21226
611	21369
612	21099
613	20969
614	20966
615	20589
616	20489
617	20917
618	20653
619	20528
620	20547
621	20572
622	20604
623	20310
624	20252
625	20170
626	19921
627	20037
628	19844
629	19779
630	19798
631	19934
632	19631
633	19615
634	19636
635	19317
636	19287
637	19284
638	19467
639	19080
640	19175
641	19229
642	19034
643	18971
644	18912
645	18891
646	18913
647	18771
648	18785
649	18478
650	18515
651	18674
652	18603
653	18460
654	18230
655	18306
656	18224
657	18359
658	18197
659	18185
660	17907
661	18125
662	18227
663	18024
664	17844
665	17950
666	17676
667	17535
668	17798
669	17606
670	17442
671	17472
672	17404
673	17299
674	17277
675	17119
676	16835
677	16976
678	16739
679	16832
680	16859
681	16738
682	16953
683	16927
684	16750
685	16765
686	16755
687	16753
688	16604
689	16554
690	16276
691	16628
692	16215
693	16327
694	16358
695	16207
696	16073
697	16229
698	15908
699	16087
700	16072
701	15890
702	15970
703	15815
704	15617
705	15777
706	15503
707	15403
708	15533
709	15807
710	15598
711	15451
712	15639
713	15465
714	15420
715	15124
716	15222
717	15048
718	15336
719	15262
720	15110
721	15390
722	14957
723	15194
724	14921
725	14834
726	14872
727	14982
728	14896
729	14545
730	14691
731	14541
732	14599
733	14420
734	14547
735	14475
736	14301
737	14438
738	14176
739	14317
740	14151
741	14391
742	14363
743	14111
744	14274
745	14080
746	13890
747	13896
748	13897
749	13965
750	13888
751	14034
752	13971
753	13765
754	13768
755	13634
756	13729
757	13603
758	13755
759	13810
760	13586
761	13379
762	13564
763	13499
764	13312
765	13370
766	13364
767	13081
768	13146
769	12902
770	13168
771	13074
772	12925
773	12930
774	12829
775	12946
776	12891
777	12786
778	12889
779	12868
780	12899
781	12883
782	12723
783	12844
784	12741
785	12587
786	12636
787	12457
788	12456
789	12499
790	12316
791	12370
792	12324
793	12261
794	12100
795	12156
796	11967
797	12114
798	12128
799	12192
800	12001
801	11950
802	11835
803	11998
804	12097
805	11941
806	11827
807	11642
808	11713
809	11849
810	11696
811	11592
812	11759
813	11513
814	11717
815	11434
816	11559
817	11468
818	11627
819	11708
820	11532
821	11718
822	11519
823	11255
824	11353
825	11529
826	11451
827	11352
828	11153
829	11328
830	11175
831	11194
832	11107
833	11172
834	11049
835	11110
836	11035
837	10938
838	11145
839	10937
840	10973
841	10908
842	10851
843	10999
844	10995
845	10764
846	10725
847	10796
848	10710
849	10643
850	10726
851	10762
852	10721
853	10754
854	10689
855	10874
856	10925
857	10631
858	10448
859	10501
860	10568
861	10547
862	10560
863	10293
864	10289
865	10204
866	10195
867	10323
868	10313
869	10241
870	10121
871	10138
872	10147
873	10077
874	9880
875	9940
876	10010
877	10058
878	9999
879	10078
880	9929
881	10285
882	10099
883	9840
884	9851
885	10022
886	9947
887	9867
888	9824
889	9981
890	9643
891	9822
892	9801
893	9788
894	9751
895	9805
896	9664
897	9735
898	9697
899	9721
900	9572
901	9521
902	9419
903	9631
904	9641
905	9608
906	9525
907	9486
908	9453
909	9547
910	9526
911	9353
912	9440
913	9116
914	9170
915	9281
916	9184
917	9235
918	9219
919	9162
920	9299
921	9255
922	9228
923	9149
924	9154
925	9230
926	9006
927	9193
928	9116
929	8992
930	8993
931	8899
932	8920
933	8854
934	9080
935	8922
936	8947
937	8874
938	8950
939	8720
940	8752
941	8822
942	8874
943	8863
944	8625
945	8750
946	8631
947	8722
948	8642
949	8674
950	8636
951	8707
952	8494
953	8649
954	8557
955	8588
956	8515
957	8552
958	8440
959	8524
960	8370
961	8651
962	8326
963	8451
964	8328
965	8337
966	8129
967	8119
968	8156
969	8084
970	8263
971	8238
972	8166
973	8277
974	8157
975	8228
976	8118
977	8131
978	8095
979	7978
980	8074
981	8124
982	8070
983	8024
984	8055
985	7873
986	7932
987	7977
988	7918
989	7996
990	7797
991	7884
992	7955
993	7775
994	7804
995	7846
996	7765
997	7832
998	7670
999	7711
1000	28119913