1	12678
2	12261
3	12229
4	12721
5	12931
6	13376
7	13814
8	14386
9	14790
10	14768
11	14379
12	14215
13	14429
14	14893
15	15336
16	15249
17	14489
18	13865
19	13652
20	13273
21	13241
22	13852
23	14566
24	15217
25	15366
26	14908
27	15002
28	14892
29	14609
30	14772
31	14810
32	14498
33	14019
34	13811
35	13793
36	13944
37	14286
38	14535
39	15007
40	15486
41	15600
42	15518
43	15184
44	14922
45	15105
46	15013
47	14548
48	14823
49	15043
50	15270
51	15764
52	15905
53	16511
54	16623
55	16384
56	16010
57	16166
58	16395
59	16685
60	17438
61	17835
62	18196
63	18847
64	19154
65	19304
66	18868
67	18451
68	18679
69	18561
70	18546
71	18945
72	19282
73	18846
74	18994
75	19159
76	19774
77	20181
78	20798
79	21111
80	21175
81	21214
82	21518
83	21887
84	22519
85	23685
86	24951
87	25580
88	26260
89	26568
90	27027
91	28248
92	29660
93	30394
94	30873
95	30368
96	30750
97	31590
98	33260
99	34734
100	35344
101	36266
102	38350
103	40574
104	42509
105	44822
106	46501
107	47814
108	48940
109	49121
110	49845
111	50332
112	52229
113	54622
114	56731
115	58802
116	60634
117	62475
118	63823
119	63880
120	64596
121	66396
122	67111
123	66693
124	65086
125	64481
126	63165
127	61493
128	60427
129	59696
130	59617
131	58528
132	56218
133	53604
134	51437
135	49852
136	48279
137	46240
138	43845
139	41812
140	41311
141	40601
142	39582
143	36833
144	34512
145	33573
146	32880
147	32286
148	32201
149	31380
150	30449
151	29609
152	28727
153	27684
154	26775
155	25520
156	25190
157	24817
158	24723
159	24633
160	24587
161	23760
162	23119
163	22719
164	22650
165	22370
166	22102
167	21693
168	21111
169	20808
170	20288
171	20018
172	20095
173	20315
174	20340
175	20827
176	20925
177	20306
178	19785
179	18985
180	18992
181	19167
182	19715
183	19329
184	19279
185	19173
186	19494
187	19961
188	19995
189	19233
190	18158
191	17219
192	16658
193	16622
194	16537
195	16668
196	16282
197	16192
198	15549
199	15253
200	14765
201	14858
202	15018
203	15269
204	15559
205	16413
206	16936
207	17376
208	17918
209	17865
210	17608
211	16848
212	16512
213	16451
214	16599
215	16605
216	16618
217	16570
218	15885
219	15531
220	15857
221	16231
222	16239
223	16080
224	16548
225	16776
226	16814
227	16657
228	17132
229	17687
230	17867
231	17518
232	16943
233	16793
234	16612
235	16973
236	17135
237	17230
238	17104
239	17262
240	17528
241	17642
242	17513
243	17181
244	16824
245	16384
246	16460
247	16384
248	16517
249	16221
250	16133
251	16362
252	17305
253	18317
254	19073
255	18963
256	18752
257	18184
258	18315
259	19288
260	19055
261	18636
262	17845
263	16714
264	16329
265	16691
266	17505
267	18060
268	18930
269	19261
270	19039
271	18856
272	19037
273	19240
274	19285
275	19566
276	19776
277	19840
278	20263
279	20460
280	20498
281	20710
282	21020
283	20991
284	20321
285	20097
286	20160
287	20966
288	21596
289	22913
290	23973
291	24422
292	24022
293	23659
294	23572
295	22571
296	22239
297	22477
298	23858
299	24962
300	25297
301	25880
302	26998
303	28249
304	28626
305	28372
306	28172
307	28522
308	28628
309	29118
310	30151
311	30414
312	31399
313	32686
314	33960
315	34282
316	34216
317	34405
318	34745
319	35238
320	35351
321	36259
322	37860
323	38024
324	37328
325	37606
326	38004
327	39223
328	38754
329	38410
330	37632
331	36930
332	36847
333	37911
334	38374
335	38810
336	38149
337	37038
338	37014
339	37765
340	38369
341	38323
342	38546
343	38350
344	38456
345	38043
346	37979
347	38232
348	38901
349	38552
350	37733
351	37591
352	37943
353	37556
354	38045
355	38253
356	39447
357	40224
358	39668
359	37366
360	36378
361	36068
362	35614
363	35236
364	34708
365	34002
366	34050
367	33970
368	34023
369	33595
370	33074
371	33044
372	32902
373	32587
374	31917
375	31814
376	31957
377	32027
378	32175
379	32512
380	33407
381	33576
382	32625
383	31715
384	31907
385	33174
386	34018
387	34227
388	34608
389	34891
390	34164
391	34271
392	34548
393	34841
394	34832
395	35079
396	36126
397	37070
398	37996
399	38259
400	39455
401	40418
402	41111
403	41435
404	41679
405	42274
406	43204
407	42544
408	42294
409	43319
410	45652
411	46789
412	46516
413	46411
414	46846
415	47486
416	48858
417	51496
418	53133
419	53810
420	53963
421	54080
422	54878
423	56245
424	57140
425	56868
426	57327
427	57564
428	58413
429	57906
430	57417
431	55705
432	54122
433	54849
434	56770
435	58383
436	58430
437	57016
438	56807
439	56343
440	56195
441	56693
442	58852
443	60531
444	61916
445	62963
446	64680
447	65334
448	66707
449	66324
450	66947
451	67513
452	67912
453	67850
454	69973
455	72604
456	75211
457	75549
458	77102
459	79024
460	81083
461	82722
462	83293
463	85639
464	89575
465	92787
466	95738
467	99331
468	102690
469	106050
470	105790
471	108261
472	110375
473	117605
474	122618
475	123855
476	124043
477	126043
478	129948
479	132750
480	135687
481	138066
482	140165
483	142095
484	144028
485	144319
486	144763
487	147779
488	152081
489	155024
490	154482
491	151973
492	150146
493	154448
494	155022
495	155113
496	155438
497	155555
498	160319
499	162543
500	165510
501	168975
502	171756
503	173962
504	175261
505	179483
506	185068
507	188766
508	195355
509	201045
510	206382
511	209384
512	213642
513	219951
514	226366
515	233452
516	233436
517	232607
518	238459
519	245976
520	255095
521	259363
522	267118
523	275084
524	286010
525	295447
526	300498
527	306519
528	313930
529	322150
530	327128
531	335641
532	342304
533	348147
534	350516
535	357915
536	371330
537	376515
538	380031
539	380825
540	381937
541	385629
542	389498
543	389662
544	385982
545	383991
546	378080
547	370497
548	366347
549	362798
550	365111
551	367343
552	362397
553	354066
554	347310
555	341165
556	336346
557	340961
558	341143
559	337175
560	337379
561	339030
562	343361
563	343696
564	352811
565	355507
566	356413
567	358887
568	366270
569	369462
570	372180
571	378354
572	382790
573	385086
574	385519
575	390877
576	390764
577	395517
578	400516
579	403179
580	400073
581	388889
582	377603
583	369389
584	362633
585	359018
586	352168
587	346904
588	337185
589	326808
590	316676
591	311526
592	301861
593	285642
594	274895
595	264871
596	254562
597	240856
598	229830
599	223255
600	217590
601	208230
602	195577
603	190422
604	186764
605	181061
606	172104
607	164697
608	159189
609	155543
610	152312
611	147784
612	142161
613	138928
614	136834
615	135598
616	130923
617	127739
618	125065
619	122141
620	116624
621	113189
622	112352
623	111660
624	109556
625	108505
626	108839
627	104651
628	102485
629	101106
630	102340
631	103859
632	102614
633	102284
634	101231
635	99845
636	100652
637	101947
638	100253
639	99137
640	99998
641	100063
642	94537
643	94770
644	98148
645	103029
646	105740
647	104205
648	103871
649	102025
650	101693
651	102195
652	102602
653	99628
654	96985
655	98936
656	99031
657	97994
658	96618
659	95092
660	93506
661	92630
662	91715
663	89352
664	88963
665	87786
666	85143
667	82888
668	79355
669	77954
670	76540
671	76113
672	75652
673	74670
674	72706
675	69894
676	68164
677	65580
678	63582
679	63713
680	62087
681	60162
682	60354
683	60900
684	60276
685	59858
686	59703
687	59235
688	58256
689	56548
690	56309
691	55055
692	54305
693	53464
694	53340
695	54685
696	54531
697	53548
698	52333
699	51005
700	49738
701	48390
702	47109
703	46247
704	45956
705	46718
706	46331
707	45513
708	46748
709	46309
710	43688
711	42947
712	42762
713	43216
714	43083
715	42524
716	41912
717	42313
718	41853
719	40232
720	39409
721	41147
722	43313
723	42334
724	42952
725	43240
726	43053
727	42084
728	41767
729	41008
730	41157
731	39855
732	38556
733	37932
734	38191
735	39082
736	38129
737	37295
738	36859
739	37313
740	36914
741	35460
742	34983
743	34516
744	34211
745	33982
746	33261
747	30908
748	30060
749	30361
750	30757
751	30545
752	30832
753	30522
754	28895
755	28645
756	26650
757	25526
758	25449
759	25714
760	24963
761	24261
762	24060
763	24086
764	23890
765	23679
766	24114
767	25116
768	24300
769	22455
770	21375
771	21982
772	22784
773	21524
774	19730
775	19028
776	19568
777	20660
778	20895
779	21467
780	22397
781	21587
782	19749
783	19690
784	19621
785	19449
786	19778
787	19184
788	17832
789	17987
790	18834
791	20012
792	19761
793	19698
794	19201
795	18847
796	18099
797	18114
798	19167
799	19533
800	18169
801	17735
802	17662
803	17390
804	17350
805	16703
806	16453
807	16599
808	16809
809	16824
810	16857
811	16971
812	16994
813	17659
814	17602
815	16645
816	16982
817	17455
818	17155
819	17845
820	19030
821	18666
822	18600
823	18353
824	17798
825	17243
826	17502
827	17760
828	16454
829	16026
830	16624
831	16299
832	15516
833	15537
834	15951
835	15658
836	15649
837	16454
838	17244
839	15769
840	15144
841	16379
842	16386
843	15442
844	14564
845	15757
846	16252
847	16355
848	16841
849	16949
850	16241
851	16133
852	16648
853	16780
854	15980
855	14172
856	13818
857	13853
858	14239
859	14889
860	15465
861	15363
862	13991
863	12854
864	13089
865	14247
866	14853
867	14430
868	14086
869	14857
870	15158
871	15159
872	15095
873	15834
874	15734
875	15402
876	14505
877	14552
878	14646
879	15250
880	14995
881	14543
882	14445
883	14037
884	14390
885	13902
886	14124
887	15450
888	16357
889	15753
890	16259
891	15951
892	14855
893	15019
894	14220
895	14025
896	14657
897	14584
898	14220
899	14047
900	13888
901	13217
902	14150
903	14080
904	14940
905	16218
906	16537
907	16404
908	15420
909	15230
910	14734
911	13969
912	14166
913	14561
914	13921
915	15108
916	15658
917	14062
918	13931
919	14127
920	14858
921	14854
922	14535
923	14284
924	15482
925	15713
926	14867
927	14601
928	15029
929	14319
930	14129
931	14315
932	13947
933	12528
934	12935
935	13871
936	12938
937	13205
938	12491
939	12202
940	11836
941	12901
942	14041
943	14206
944	14147
945	13586
946	13435
947	12842
948	13371
949	15244
950	14851
951	14460
952	15070
953	14937
954	14451
955	13122
956	14156
957	14331
958	13877
959	13251
960	13171
961	12843
962	12655
963	13296
964	13288
965	13845
966	14949
967	13999
968	12770
969	12998
970	13384
971	13777
972	13882
973	14017
974	13305
975	14669
976	14845
977	13591
978	12571
979	12322
980	12922
981	13974
982	14899
983	14414
984	13494
985	12991
986	13186
987	13839
988	14301
989	14879
990	14219
991	14129
992	13765
993	14122
994	14747
995	15206
996	13890
997	13137
998	12894
999	12689
1000	13812
1001	14159
1002	14163
1003	13700
1004	13717
1005	13970
1006	14004
1007	13479
1008	13975
1009	13513
1010	13595
1011	13816
1012	14481
1013	14402
1014	13964
1015	13929
1016	13455
1017	13482
1018	13293
1019	13567
1020	13957
1021	12616
1022	12274
1023	13628
1024	15779