1	9001
2	9954
3	9833
4	8849
5	7462
6	6351
7	5856
8	5365
9	5420
10	5986
11	6591
12	6635
13	6052
14	4998
15	4705
16	5000
17	5316
18	5888
19	6884
20	7471
21	7492
22	6870
23	5446
24	4346
25	3887
26	3782
27	4154
28	4762
29	5062
30	5424
31	5419
32	5435
33	5338
34	5799
35	5962
36	5726
37	5297
38	5156
39	5444
40	5699
41	6008
42	6021
43	5522
44	4946
45	4548
46	4220
47	4335
48	4299
49	4525
50	4320
51	4462
52	4251
53	4355
54	4663
55	4586
56	5205
57	5669
58	6091
59	6225
60	5576
61	4857
62	4627
63	5199
64	5595
65	5661
66	5728
67	5070
68	4824
69	5479
70	6858
71	7980
72	8051
73	7546
74	7003
75	6595
76	6398
77	5862
78	5245
79	4730
80	4736
81	5633
82	6743
83	7428
84	7747
85	7266
86	6944
87	7059
88	7182
89	6769
90	6342
91	5964
92	6173
93	6559
94	6867
95	6731
96	6594
97	6130
98	5667
99	6236
100	6600
101	6930
102	7167
103	7870
104	8611
105	9431
106	9787
107	9747
108	9473
109	9195
110	9970
111	11344
112	11827
113	10386
114	8350
115	6687
116	6367
117	6985
118	7435
119	6870
120	5937
121	5093
122	4620
123	5159
124	6444
125	8524
126	10679
127	12209
128	11973
129	10953
130	9544
131	8495
132	7573
133	6733
134	6364
135	7117
136	8452
137	9358
138	9451
139	8573
140	7627
141	7049
142	7448
143	8905
144	10320
145	10660
146	10859
147	10656
148	11119
149	11307
150	11295
151	10621
152	11180
153	11357
154	11605
155	11057
156	10454
157	9450
158	8728
159	7683
160	7282
161	7530
162	8341
163	8998
164	9067
165	8928
166	9218
167	9725
168	9646
169	8707
170	7805
171	7402
172	7502
173	8155
174	8672
175	9183
176	10564
177	11801
178	12344
179	12883
180	13687
181	14443
182	14891
183	15027
184	13705
185	12288
186	11230
187	10915
188	11162
189	11554
190	11868
191	11323
192	10120
193	9294
194	9568
195	10247
196	9839
197	9259
198	8861
199	8701
200	8710
201	9205
202	9813
203	11028
204	11438
205	11345
206	10352
207	9450
208	9604
209	10471
210	11299
211	12292
212	13198
213	12843
214	11031
215	9450
216	8242
217	8022
218	8225
219	9850
220	11509
221	13801
222	14424
223	13962
224	12085
225	11357
226	11478
227	11454
228	12075
229	12692
230	13996
231	14581
232	14108
233	12105
234	10856
235	10843
236	11295
237	10670
238	10385
239	10570
240	11141
241	11649
242	11385
243	11626
244	11548
245	11243
246	10660
247	10099
248	10581
249	11739
250	12202
251	11942
252	11502
253	11190
254	11425
255	10968
256	11139
257	11304
258	11211
259	11726
260	11609
261	11521
262	11523
263	11494
264	10877
265	9123
266	7741
267	7546
268	8960
269	10481
270	11508
271	11793
272	11377
273	10701
274	9922
275	8608
276	8619
277	8871
278	9304
279	8958
280	8468
281	7755
282	7059
283	6553
284	5695
285	5831
286	6697
287	8245
288	9663
289	10703
290	10466
291	8878
292	7746
293	8072
294	9689
295	11071
296	11114
297	10034
298	9780
299	10551
300	10804
301	10087
302	9171
303	9640
304	11222
305	12507
306	12696
307	12804
308	12397
309	11667
310	10975
311	11344
312	11848
313	12626
314	11953
315	10120
316	7625
317	6349
318	6552
319	7122
320	7974
321	8031
322	8052
323	9352
324	11658
325	12061
326	10837
327	9978
328	9918
329	10848
330	10912
331	9815
332	9192
333	9012
334	9363
335	9994
336	9912
337	9295
338	8975
339	9580
340	9926
341	9446
342	8926
343	8946
344	9633
345	10555
346	11775
347	13684
348	15265
349	16445
350	17031
351	16698
352	15663
353	14133
354	13673
355	14371
356	15111
357	14093
358	11257
359	8786
360	9484
361	10436
362	10049
363	8617
364	7435
365	7396
366	7556
367	7805
368	8382
369	9864
370	11482
371	12450
372	13265
373	14395
374	14289
375	12920
376	12144
377	12283
378	12530
379	12442
380	12064
381	12047
382	12712
383	13306
384	13679
385	13847
386	13869
387	13137
388	12971
389	12625
390	12505
391	13152
392	14361
393	15045
394	14733
395	14157
396	14844
397	14893
398	13822
399	13480
400	14721
401	15939
402	16517
403	16168
404	15095
405	14609
406	13434
407	11763
408	11102
409	11930
410	13097
411	13516
412	14750
413	15521
414	15495
415	14036
416	12647
417	12070
418	13538
419	16119
420	18240
421	17972
422	16773
423	15566
424	14821
425	13530
426	12237
427	11434
428	12196
429	13331
430	15518
431	16712
432	16491
433	15179
434	14196
435	12801
436	11891
437	12688
438	13478
439	12663
440	11756
441	11602
442	13526
443	15698
444	16367
445	14484
446	12338
447	11429
448	12640
449	14868
450	15082
451	13860
452	12874
453	13264
454	14558
455	15743
456	15501
457	15520
458	15310
459	14704
460	14213
461	14690
462	15197
463	14743
464	15925
465	16775
466	15805
467	13888
468	13025
469	14207
470	14345
471	13041
472	11371
473	10747
474	11584
475	13652
476	16478
477	16627
478	15329
479	14860
480	16197
481	19233
482	19881
483	18266
484	16734
485	14899
486	13105
487	12670
488	13610
489	14509
490	15503
491	16311
492	15546
493	15691
494	15821
495	15255
496	14697
497	15195
498	16059
499	14840
500	13690
501	14774
502	15883
503	14339
504	13366
505	13605
506	14035
507	12898
508	11509
509	11729
510	11542
511	10233
512	10174
513	11232
514	11317
515	11427
516	11906
517	11093
518	9757
519	10205
520	12934
521	14037
522	13423
523	12055
524	11350
525	10645
526	8646
527	8986
528	10032
529	9301
530	8503
531	8569
532	9241
533	9890
534	9363
535	8968
536	9794
537	10536
538	10281
539	9833
540	10472
541	11143
542	11307
543	11477
544	10571
545	9531
546	9253
547	10633
548	10234
549	9195
550	10236
551	13439
552	16088
553	15417
554	12407
555	11000
556	10826
557	10581
558	8696
559	7255
560	6869
561	7931
562	8131
563	6261
564	5835
565	7084
566	8338
567	8943
568	9554
569	9353
570	9146
571	9514
572	9382
573	9239
574	10135
575	11375
576	12101
577	11242
578	9869
579	8938
580	7233
581	5527
582	5674
583	6734
584	7226
585	7773
586	8275
587	9334
588	10722
589	11040
590	12029
591	12448
592	12510
593	12671
594	13535
595	13691
596	11243
597	8831
598	8828
599	9587
600	11244
601	11960
602	9354
603	7502
604	7910
605	7439
606	6040
607	5861
608	7890
609	10205
610	10065
611	8332
612	7434
613	8223
614	9573
615	9186
616	6953
617	6615
618	7860
619	9886
620	10029
621	8609
622	8463
623	8470
624	6827
625	4867
626	4308
627	4509
628	5093
629	4981
630	5315
631	6044
632	6257
633	7893
634	8977
635	9606
636	10454
637	12735
638	11426
639	7049
640	6234
641	8090
642	7792
643	6260
644	5452
645	5627
646	5341
647	5891
648	6966
649	7200
650	6599
651	5189
652	5338
653	6304
654	7307
655	6698
656	5699
657	5617
658	5631
659	5841
660	4629
661	3955
662	6488
663	9087
664	9408
665	8663
666	7852
667	6090
668	5475
669	4726
670	3888
671	4101
672	4743
673	5499
674	6550
675	6746
676	7088
677	6435
678	5618
679	5755
680	5470
681	6026
682	8216
683	10214
684	9631
685	9433
686	9881
687	8186
688	6570
689	6980
690	6571
691	6141
692	5975
693	5996
694	7790
695	9767
696	9150
697	7769
698	7260
699	6945
700	7643
701	9789
702	11646
703	9919
704	8456
705	9279
706	11223
707	10437
708	9590
709	7983
710	7445
711	7797
712	7317
713	6468
714	6369
715	8043
716	8227
717	7511
718	9483
719	9496
720	8485
721	8681
722	8286
723	9336
724	11950
725	11628
726	12201
727	13598
728	13062
729	12160
730	9860
731	10064
732	10474
733	9826
734	8797
735	8090
736	9428
737	9935
738	10006
739	11417
740	15111
741	15661
742	13869
743	12409
744	11517
745	12328
746	12559
747	12133
748	11646
749	10758
750	10612
751	10664
752	10176
753	9778
754	9706
755	10098
756	8514
757	6846
758	7161
759	8080
760	8315
761	7923
762	7276
763	9252
764	9964
765	9934
766	12555
767	14787
768	12269
769	8453
770	7376
771	7113
772	6797
773	7214
774	8832
775	9403
776	8728
777	9482
778	10512
779	9664
780	9864
781	9991
782	10419
783	10325
784	11008
785	11918
786	11011
787	10057
788	9338
789	9485
790	9142
791	11463
792	12713
793	10663
794	9428
795	10147
796	10824
797	9067
798	6623
799	7243
800	8305
801	7487
802	7995
803	8693
804	8166
805	6470
806	7010
807	8291
808	9845
809	11675
810	10271
811	8041
812	7424
813	7321
814	6212
815	6738
816	7981
817	8507
818	10548
819	11591
820	9292
821	9109
822	11125
823	10862
824	9445
825	8244
826	7184
827	6847
828	4031
829	4129
830	6440
831	7508
832	8325
833	9475
834	8779
835	7298
836	7982
837	8702
838	9758
839	8547
840	7358
841	6408
842	5041
843	4723
844	3982
845	4517
846	6030
847	6775
848	5758
849	4265
850	3061
851	3595
852	4673
853	5071
854	6800
855	9076
856	8017
857	5372
858	4016
859	3188
860	3248
861	3789
862	5095
863	5264
864	5702
865	5616
866	4599
867	3975
868	4842
869	5299
870	4850
871	4760
872	5725
873	6075
874	6492
875	7839
876	5884
877	5568
878	6863
879	8316
880	9727
881	8517
882	4827
883	3707
884	4911
885	5624
886	5296
887	4747
888	4238
889	5506
890	6842
891	5547
892	3907
893	3501
894	3092
895	3646
896	5936
897	5378
898	6895
899	5968
900	5004
901	4356
902	5995
903	7741
904	5608
905	4694
906	5087
907	4734
908	4166
909	4083
910	4065
911	5258
912	4942
913	4086
914	3929
915	4315
916	6316
917	7345
918	5201
919	3202
920	4586
921	5588
922	6163
923	6989
924	4947
925	3649
926	4441
927	3894
928	3995
929	4121
930	3235
931	3049
932	3084
933	4745
934	4739
935	4000
936	4060
937	4278
938	4165
939	3543
940	4087
941	4985
942	6653
943	6923
944	7195
945	5222
946	3458
947	3815
948	3861
949	2824
950	2575
951	2014
952	2610
953	4634
954	6213
955	5520
956	4408
957	5377
958	5771
959	4137
960	3942
961	5297
962	6124
963	3687
964	2721
965	3083
966	3530
967	3778
968	4109
969	3743
970	2564
971	2055
972	2164
973	3618
974	5192
975	5523
976	4940
977	7060
978	6349
979	2603
980	2658
981	4546
982	4233
983	5142
984	4761
985	3428
986	1977
987	2348
988	2901
989	2977
990	4566
991	5398
992	4426
993	3956
994	5654
995	5461
996	3607
997	3503
998	3381
999	4448
1000	4261
1001	2970
1002	3288
1003	4402
1004	3759
1005	2545
1006	2779
1007	2853
1008	2977
1009	2849
1010	3075
1011	2941
1012	2917
1013	3393
1014	4472
1015	4487
1016	3019
1017	1940
1018	1860
1019	2248
1020	2933
1021	2415
1022	3693
1023	4035
1024	4287