1	9780
2	10048
3	10464
4	10458
5	10311
6	10109
7	10020
8	10179
9	10185
10	9938
11	9729
12	9594
13	9664
14	10261
15	10606
16	10914
17	10760
18	10420
19	10265
20	10388
21	10264
22	10130
23	10050
24	9875
25	9563
26	9310
27	9362
28	9692
29	10007
30	10795
31	11100
32	11499
33	11557
34	11382
35	11485
36	11368
37	11179
38	10495
39	10047
40	9754
41	9874
42	9968
43	9832
44	9702
45	9722
46	9596
47	9796
48	10470
49	11078
50	11162
51	11459
52	11548
53	12248
54	12659
55	12991
56	13132
57	12721
58	12171
59	11810
60	11940
61	12252
62	12371
63	12536
64	12314
65	12463
66	12663
67	12868
68	12931
69	12938
70	12985
71	13984
72	14478
73	14988
74	15228
75	15523
76	16059
77	15991
78	16301
79	17070
80	17694
81	18542
82	19455
83	20446
84	21250
85	22584
86	25245
87	27836
88	30334
89	32460
90	34551
91	36250
92	38922
93	41308
94	43228
95	45095
96	46637
97	47782
98	49472
99	50089
100	50162
101	48366
102	45590
103	42623
104	39127
105	36684
106	34309
107	31691
108	29360
109	26626
110	24925
111	23019
112	21588
113	20213
114	19050
115	18386
116	17897
117	17733
118	17295
119	16383
120	15487
121	15176
122	14882
123	14590
124	14437
125	14416
126	14141
127	13372
128	12827
129	12289
130	12063
131	11872
132	11849
133	11911
134	11947
135	12184
136	11942
137	11948
138	11904
139	11885
140	12098
141	12235
142	12576
143	12502
144	12471
145	12324
146	11734
147	11035
148	11219
149	11174
150	11506
151	11676
152	11383
153	11133
154	11473
155	11742
156	11953
157	12032
158	11595
159	11644
160	11398
161	11343
162	11367
163	11159
164	11305
165	11280
166	11553
167	11816
168	11815
169	12018
170	11739
171	11115
172	10695
173	10944
174	11679
175	12001
176	11881
177	11231
178	10939
179	10896
180	11137
181	10960
182	11731
183	11796
184	11841
185	12019
186	12002
187	11708
188	11422
189	11202
190	11053
191	10843
192	10622
193	11003
194	11050
195	11555
196	11797
197	11890
198	11534
199	11562
200	11395
201	11475
202	11892
203	11988
204	12284
205	12602
206	12406
207	11994
208	11706
209	12043
210	12615
211	13394
212	14056
213	13914
214	14056
215	14114
216	14661
217	15002
218	15140
219	15503
220	15464
221	16409
222	17223
223	18500
224	19235
225	19838
226	20525
227	21045
228	22175
229	23003
230	24206
231	25407
232	26354
233	27888
234	28923
235	30340
236	30899
237	30014
238	28925
239	27452
240	26631
241	25192
242	23659
243	22355
244	21349
245	20050
246	19379
247	18573
248	17512
249	16774
250	16527
251	16283
252	16063
253	15387
254	14268
255	13786
256	13248
257	13291
258	13897
259	14572
260	14222
261	13166
262	12570
263	12469
264	13287
265	13855
266	14087
267	13724
268	14113
269	14105
270	13961
271	13849
272	13750
273	14039
274	13578
275	13486
276	12780
277	12465
278	12228
279	12150
280	11905
281	11553
282	11354
283	11445
284	11400
285	11436
286	11274
287	11246
288	11230
289	11256
290	11081
291	11048
292	10853
293	11095
294	10891
295	11137
296	11767
297	12599
298	12731
299	12828
300	13724
301	14410
302	14977
303	15503
304	15840
305	15353
306	14813
307	15047
308	14637
309	14139
310	13143
311	12340
312	12530
313	13124
314	13991
315	13963
316	13714
317	13130
318	12609
319	12497
320	12245
321	12042
322	12661
323	13109
324	13347
325	13258
326	13008
327	12818
328	12514
329	12823
330	13782
331	14810
332	15077
333	15063
334	14905
335	15750
336	16398
337	16638
338	16725
339	17190
340	17467
341	17505
342	17252
343	16446
344	15872
345	15505
346	15614
347	16114
348	16578
349	16752
350	16022
351	15352
352	14661
353	14397
354	14762
355	14785
356	14895
357	15569
358	15950
359	15747
360	15164
361	13903
362	13255
363	13227
364	14089
365	14347
366	14628
367	14203
368	13454
369	12995
370	13164
371	13136
372	12779
373	12625
374	12640
375	12692
376	12650
377	12071
378	11698
379	11393
380	11720
381	11764
382	11780
383	12012
384	11869
385	11599
386	11331
387	11512
388	11562
389	12188
390	11984
391	12166
392	12238
393	12011
394	11972
395	12296
396	12259
397	11959
398	11806
399	11801
400	12133
401	12273
402	12170
403	12221
404	12340
405	12321
406	12248
407	11793
408	12137
409	12339
410	12546
411	12466
412	12680
413	13037
414	13171
415	13338
416	13167
417	13041
418	12940
419	13088
420	13008
421	12641
422	12562
423	12337
424	12067
425	12139
426	12359
427	12395
428	12246
429	12320
430	12234
431	12524
432	12364
433	12195
434	11645
435	10947
436	10691
437	10640
438	11097
439	11384
440	11770
441	12196
442	12318
443	12208
444	11740
445	11294
446	11714
447	11584
448	11470
449	11502
450	12367
451	12522
452	12191
453	11839
454	11936
455	12391
456	12962
457	13356
458	13149
459	13215
460	13212
461	13556
462	12947
463	12469
464	12146
465	11939
466	12372
467	12821
468	13189
469	13500
470	13697
471	14443
472	14293
473	14073
474	14171
475	14639
476	15426
477	16435
478	16105
479	15606
480	15685
481	15962
482	15468
483	14897
484	14457
485	14056
486	14084
487	14305
488	14311
489	14392
490	13603
491	12978
492	12653
493	12686
494	12288
495	12355
496	12448
497	12161
498	11428
499	10889
500	10822
501	11595
502	12585
503	12457
504	11896
505	12345
506	12739
507	12857
508	13062
509	13501
510	13696
511	13167
512	12453
513	11964
514	10957
515	11195
516	12376
517	13888
518	14086
519	13455
520	12775
521	12644
522	12890
523	13217
524	13479
525	13833
526	14180
527	14122
528	13911
529	13109
530	12738
531	12825
532	12807
533	12994
534	12973
535	12819
536	13249
537	13309
538	13770
539	14161
540	14311
541	14022
542	13910
543	13462
544	13243
545	12990
546	12462
547	12181
548	12095
549	12081
550	12198
551	12759
552	13366
553	13784
554	14078
555	13410
556	13090
557	13038
558	13520
559	14324
560	14167
561	13940
562	15008
563	15045
564	14384
565	13666
566	13983
567	14908
568	15661
569	15877
570	16218
571	15924
572	15558
573	16052
574	15706
575	14293
576	13464
577	14101
578	15261
579	16198
580	16179
581	15471
582	15325
583	15851
584	16459
585	16592
586	16405
587	16577
588	17090
589	17476
590	17355
591	18032
592	18979
593	19549
594	19251
595	18017
596	17382
597	17599
598	18504
599	19939
600	20298
601	19984
602	19601
603	18671
604	17527
605	16996
606	17168
607	17983
608	19313
609	20304
610	20495
611	20525
612	20369
613	20834
614	20205
615	20048
616	21011
617	22049
618	22410
619	23300
620	23615
621	24271
622	24793
623	24358
624	24256
625	24789
626	24502
627	24069
628	24225
629	24650
630	25954
631	26065
632	25803
633	25354
634	25012
635	25306
636	26157
637	26883
638	26768
639	27055
640	26715
641	25968
642	26811
643	29815
644	31954
645	32414
646	32266
647	32248
648	33706
649	34595
650	34795
651	36061
652	37105
653	36840
654	37500
655	39791
656	41832
657	43584
658	43457
659	42485
660	42931
661	45223
662	46953
663	46521
664	47762
665	47944
666	48167
667	49561
668	50865
669	52970
670	54163
671	54382
672	56307
673	58662
674	62144
675	63501
676	63824
677	64213
678	64647
679	67663
680	72254
681	75303
682	78809
683	80887
684	79805
685	80020
686	83231
687	85797
688	88456
689	90809
690	95140
691	96676
692	97498
693	99593
694	103253
695	103824
696	106127
697	108388
698	105361
699	101987
700	101333
701	105075
702	110186
703	111045
704	109470
705	110239
706	112867
707	113616
708	113179
709	117504
710	120168
711	118934
712	117160
713	117166
714	115915
715	117772
716	117204
717	117091
718	118743
719	119789
720	118530
721	115915
722	112735
723	112810
724	115735
725	116810
726	119013
727	117664
728	114501
729	108750
730	104926
731	102093
732	99804
733	98302
734	93184
735	91344
736	90379
737	89225
738	86169
739	83375
740	78998
741	75882
742	77014
743	74731
744	70498
745	67960
746	66063
747	64313
748	63372
749	62857
750	62323
751	60933
752	57704
753	56276
754	57385
755	57266
756	55641
757	55814
758	55810
759	56981
760	55284
761	52112
762	49846
763	47530
764	47895
765	49769
766	48520
767	48559
768	49270
769	47887
770	47649
771	47006
772	46262
773	46714
774	46834
775	45809
776	43892
777	42092
778	41675
779	41329
780	42055
781	42132
782	42774
783	42710
784	41551
785	42795
786	43903
787	43672
788	41562
789	39414
790	38230
791	38823
792	39387
793	40808
794	43259
795	43596
796	41971
797	41900
798	40843
799	38842
800	38268
801	41064
802	43734
803	42693
804	40324
805	40887
806	41711
807	42370
808	43337
809	43997
810	43664
811	41473
812	41064
813	41545
814	42557
815	42352
816	40367
817	38874
818	39856
819	41462
820	40653
821	41094
822	43414
823	44866
824	44140
825	43626
826	43264
827	44105
828	46310
829	44408
830	41671
831	40776
832	39217
833	39407
834	39850
835	38370
836	37285
837	37405
838	37252
839	37785
840	38005
841	34403
842	33444
843	33278
844	33078
845	34192
846	35402
847	35630
848	33917
849	30830
850	30329
851	31479
852	30257
853	27453
854	26658
855	27653
856	27946
857	26186
858	24485
859	25151
860	25693
861	24613
862	24294
863	24300
864	24449
865	24921
866	24190
867	22599
868	22990
869	24621
870	24825
871	23934
872	22733
873	22713
874	23105
875	22851
876	20997
877	20689
878	20913
879	20729
880	20955
881	20936
882	20320
883	18574
884	19636
885	20654
886	19086
887	18617
888	19644
889	19313
890	18665
891	19156
892	18388
893	17497
894	17628
895	18240
896	19092
897	18315
898	17439
899	17302
900	17435
901	18315
902	17058
903	16743
904	18395
905	16384
906	15657
907	16920
908	17492
909	17855
910	17419
911	17191
912	17217
913	17315
914	16579
915	16558
916	16892
917	15712
918	15790
919	16223
920	16606
921	17172
922	16871
923	16148
924	16011
925	16510
926	15887
927	14545
928	14425
929	15265
930	17011
931	16435
932	14697
933	15419
934	16340
935	16817
936	17374
937	17403
938	16381
939	16175
940	17763
941	18537
942	17550
943	17666
944	18252
945	17563
946	17678
947	17125
948	16793
949	17267
950	16707
951	16957
952	16181
953	17163
954	18664
955	18576
956	17782
957	17211
958	16529
959	17820
960	18651
961	18007
962	17860
963	17010
964	17887
965	18771
966	18759
967	18879
968	17474
969	16499
970	17515
971	17954
972	18828
973	17765
974	17447
975	18878
976	17881
977	17496
978	17307
979	16784
980	16168
981	17020
982	17820
983	17771
984	18188
985	16970
986	16233
987	16875
988	15950
989	14699
990	14518
991	14798
992	15583
993	16806
994	16228
995	14956
996	16488
997	15873
998	14883
999	13284
1000	12672
1001	14095
1002	14254
1003	13943
1004	13875
1005	13824
1006	14422
1007	14557
1008	13681
1009	14293
1010	14233
1011	13367
1012	12993
1013	13453
1014	12924
1015	13126
1016	12146
1017	11947
1018	13095
1019	13204
1020	12987
1021	12763
1022	12915
1023	12732
1024	12251