1	8734
2	8584
3	8785
4	8898
5	9036
6	8994
7	8914
8	8912
9	8922
10	8718
11	8511
12	8323
13	8558
14	9030
15	9300
16	9314
17	9221
18	9071
19	8901
20	8773
21	8802
22	8912
23	9439
24	9691
25	9973
26	10189
27	10129
28	10128
29	9702
30	9790
31	9677
32	9799
33	9674
34	9175
35	8872
36	8390
37	8205
38	7779
39	8006
40	8189
41	8379
42	8744
43	8846
44	8879
45	9415
46	9569
47	9676
48	9749
49	9434
50	9236
51	9162
52	9042
53	9548
54	9965
55	10178
56	10047
57	10264
58	10360
59	10570
60	10810
61	10939
62	10752
63	10828
64	10478
65	10343
66	10352
67	10456
68	10888
69	10994
70	11315
71	11535
72	11565
73	11579
74	11825
75	12356
76	13101
77	13784
78	14169
79	14709
80	15291
81	15410
82	16474
83	17276
84	18251
85	19407
86	21014
87	22962
88	24963
89	26987
90	29540
91	31824
92	34708
93	37304
94	40015
95	41685
96	43183
97	43777
98	44219
99	43080
100	41731
101	39664
102	38665
103	37427
104	34494
105	31401
106	28297
107	26426
108	24569
109	22456
110	20679
111	19082
112	17789
113	16556
114	15546
115	15074
116	14537
117	14374
118	14057
119	13652
120	13507
121	13407
122	13001
123	12396
124	12312
125	12102
126	12037
127	11808
128	11650
129	11210
130	10888
131	10679
132	10162
133	9590
134	9184
135	9629
136	9915
137	10078
138	9930
139	9477
140	9693
141	9787
142	10007
143	10139
144	10411
145	10936
146	10413
147	10088
148	9929
149	9483
150	9011
151	8968
152	8858
153	8814
154	9176
155	9445
156	9637
157	10019
158	10125
159	10271
160	10005
161	9538
162	9519
163	9581
164	9579
165	9729
166	9997
167	10010
168	9804
169	10209
170	10366
171	10381
172	9881
173	9453
174	9375
175	9401
176	9397
177	9614
178	9516
179	9662
180	9866
181	9871
182	10038
183	9589
184	9583
185	9943
186	9802
187	9590
188	9274
189	9071
190	8828
191	9109
192	9539
193	9937
194	9615
195	9587
196	9196
197	9318
198	9280
199	9675
200	9851
201	10132
202	10325
203	10549
204	10652
205	11327
206	11290
207	10917
208	10474
209	10618
210	10890
211	11544
212	12118
213	12403
214	12948
215	12793
216	12517
217	12929
218	13778
219	14792
220	15146
221	15793
222	15635
223	16022
224	16254
225	16642
226	17201
227	17938
228	19382
229	21375
230	23372
231	24694
232	25434
233	25994
234	25601
235	25954
236	26315
237	26161
238	25945
239	24490
240	22917
241	20908
242	18773
243	17699
244	17570
245	17271
246	17100
247	16441
248	15177
249	14580
250	13975
251	13465
252	12706
253	12138
254	11933
255	12207
256	12176
257	12307
258	11997
259	11808
260	11404
261	10817
262	10876
263	10781
264	11085
265	11249
266	11613
267	11822
268	12509
269	12915
270	13011
271	13130
272	12706
273	12332
274	11745
275	11978
276	11722
277	11255
278	10723
279	10589
280	10637
281	10308
282	10197
283	10216
284	10311
285	10707
286	10413
287	9920
288	9411
289	9606
290	10003
291	10248
292	9968
293	10237
294	10515
295	10812
296	10656
297	10744
298	11348
299	11603
300	12093
301	12492
302	12763
303	12891
304	12947
305	12982
306	12990
307	12703
308	12094
309	11820
310	12001
311	11678
312	11978
313	12021
314	11905
315	11341
316	11122
317	10775
318	10823
319	11043
320	11287
321	11492
322	11587
323	11442
324	11316
325	12013
326	12463
327	12910
328	12933
329	12488
330	12129
331	12208
332	12398
333	12814
334	12792
335	12958
336	13206
337	13482
338	13894
339	14887
340	15046
341	14824
342	14211
343	13729
344	13575
345	13695
346	13797
347	13830
348	13561
349	13100
350	12811
351	12966
352	12732
353	12351
354	12224
355	12127
356	12216
357	12988
358	13917
359	13434
360	12686
361	11494
362	11185
363	10993
364	11057
365	10522
366	10479
367	10574
368	10454
369	10344
370	10144
371	10005
372	9993
373	10456
374	10591
375	10512
376	9758
377	8808
378	8809
379	8760
380	9139
381	9281
382	9253
383	9314
384	9310
385	9566
386	9180
387	8730
388	8858
389	9708
390	10337
391	10390
392	10195
393	9913
394	10315
395	10965
396	11500
397	11241
398	10897
399	10773
400	10950
401	11164
402	10870
403	10497
404	9893
405	9752
406	9965
407	9938
408	9886
409	9733
410	10018
411	10709
412	11120
413	11446
414	10856
415	10541
416	10123
417	9829
418	10035
419	10528
420	10371
421	9909
422	10165
423	10426
424	10778
425	10584
426	10524
427	10666
428	10612
429	11004
430	11164
431	11078
432	10884
433	11273
434	11284
435	10853
436	10544
437	10614
438	10531
439	9629
440	9555
441	9404
442	9462
443	10049
444	10334
445	10170
446	9985
447	10106
448	10741
449	11026
450	11078
451	10889
452	10402
453	10553
454	11230
455	11517
456	11257
457	11089
458	11042
459	11241
460	11115
461	10974
462	10887
463	10812
464	10870
465	10984
466	11628
467	11569
468	11273
469	11461
470	11256
471	11708
472	11876
473	12198
474	13233
475	14578
476	14903
477	14565
478	14112
479	13807
480	13813
481	13872
482	13225
483	12988
484	12846
485	12540
486	11741
487	11109
488	11115
489	11304
490	11228
491	11186
492	11575
493	12100
494	12100
495	12022
496	12142
497	11696
498	11186
499	11032
500	11134
501	11074
502	11034
503	11106
504	10929
505	11085
506	11525
507	11567
508	11211
509	10876
510	10729
511	11135
512	11647
513	11410
514	10798
515	10657
516	10556
517	10294
518	10991
519	11572
520	11245
521	11001
522	11243
523	11711
524	12377
525	12103
526	11683
527	11647
528	11486
529	11001
530	11132
531	11586
532	11893
533	11982
534	11351
535	11049
536	11245
537	10697
538	10759
539	11276
540	11491
541	11423
542	11288
543	11176
544	11163
545	11619
546	11502
547	11868
548	12219
549	11807
550	11772
551	11875
552	11364
553	10928
554	10845
555	10803
556	10829
557	11091
558	11603
559	12128
560	12150
561	11903
562	12309
563	12151
564	12460
565	12554
566	11782
567	11371
568	11959
569	11961
570	11574
571	11863
572	12970
573	13522
574	12594
575	11915
576	12077
577	13461
578	14562
579	14662
580	14336
581	15084
582	15087
583	14742
584	14353
585	13885
586	14119
587	13748
588	13443
589	13840
590	13907
591	14077
592	14756
593	15140
594	14973
595	14839
596	14879
597	14593
598	14907
599	14744
600	14569
601	14959
602	15672
603	16986
604	17376
605	16965
606	16695
607	16714
608	16758
609	17010
610	16900
611	16538
612	16607
613	17530
614	17553
615	17475
616	17435
617	17671
618	17736
619	18299
620	19080
621	20081
622	20272
623	20760
624	20723
625	19986
626	19715
627	20200
628	20944
629	21165
630	21612
631	21607
632	22655
633	23302
634	22441
635	22259
636	22730
637	22558
638	22320
639	24348
640	24514
641	24358
642	25202
643	25571
644	24847
645	25697
646	28143
647	29299
648	29812
649	29254
650	29503
651	29793
652	29615
653	29585
654	30615
655	32481
656	33888
657	35981
658	35813
659	35048
660	36415
661	38705
662	39816
663	39131
664	39055
665	39773
666	42328
667	42723
668	42586
669	43623
670	45370
671	48053
672	51060
673	53042
674	53312
675	52210
676	52077
677	53621
678	55400
679	57500
680	59091
681	60643
682	62177
683	65555
684	67636
685	72617
686	75302
687	72469
688	73574
689	77429
690	80483
691	81197
692	83171
693	85534
694	86753
695	88035
696	88973
697	87502
698	86773
699	90509
700	93290
701	93926
702	93739
703	93441
704	97018
705	100094
706	99040
707	97673
708	97208
709	99309
710	102729
711	105144
712	104793
713	103758
714	104118
715	104716
716	102780
717	102029
718	101707
719	102574
720	103260
721	102008
722	101323
723	102129
724	103597
725	101663
726	101126
727	100666
728	101265
729	98106
730	95697
731	92077
732	87414
733	85608
734	83794
735	83806
736	80550
737	76267
738	72110
739	65872
740	64353
741	64279
742	65577
743	64071
744	61577
745	59791
746	59446
747	56496
748	54279
749	54127
750	54491
751	54307
752	53939
753	52955
754	53366
755	51784
756	48722
757	46640
758	45515
759	45722
760	43350
761	44617
762	45172
763	44809
764	44706
765	45593
766	45836
767	45475
768	44937
769	42577
770	41564
771	42476
772	42080
773	39880
774	37719
775	37502
776	36356
777	37269
778	36604
779	35367
780	36476
781	36725
782	35965
783	36066
784	36353
785	37218
786	36795
787	36165
788	35603
789	35620
790	34269
791	34198
792	34130
793	33627
794	33616
795	34380
796	35000
797	35202
798	35043
799	34602
800	33955
801	35192
802	36894
803	36230
804	35938
805	36046
806	35420
807	34447
808	33085
809	33899
810	36293
811	36046
812	35106
813	36629
814	37688
815	37291
816	37552
817	37183
818	36488
819	37513
820	38282
821	37915
822	38433
823	38222
824	38364
825	38615
826	37253
827	37201
828	35273
829	33108
830	32601
831	32505
832	33026
833	33505
834	35242
835	35228
836	34607
837	34850
838	34061
839	34028
840	33918
841	32464
842	30033
843	28787
844	29612
845	29205
846	29167
847	29107
848	27427
849	27137
850	28467
851	28285
852	26477
853	24232
854	25525
855	26022
856	25168
857	24543
858	23682
859	22767
860	21140
861	20938
862	21234
863	20278
864	19908
865	19968
866	20068
867	20748
868	20234
869	18611
870	19544
871	20144
872	20182
873	20469
874	21004
875	19899
876	18363
877	18599
878	19188
879	18736
880	18387
881	17088
882	16635
883	18010
884	16994
885	15826
886	15844
887	17334
888	17257
889	16979
890	16796
891	17153
892	16690
893	17034
894	15623
895	15093
896	15501
897	15903
898	16381
899	15711
900	14807
901	14270
902	14798
903	14763
904	15062
905	15044
906	14650
907	14270
908	13905
909	15253
910	15525
911	15752
912	15973
913	15437
914	14913
915	14542
916	15893
917	16365
918	14684
919	13546
920	13077
921	13313
922	13784
923	14571
924	15000
925	14843
926	13927
927	13660
928	13806
929	13261
930	13960
931	13931
932	14229
933	14830
934	14692
935	14870
936	15687
937	15105
938	14399
939	14251
940	13940
941	12905
942	13926
943	15230
944	14991
945	13642
946	14595
947	15231
948	14549
949	14559
950	14958
951	14954
952	14328
953	14951
954	14861
955	14709
956	15255
957	14806
958	14887
959	15740
960	16508
961	16516
962	16512
963	17551
964	17955
965	16837
966	16471
967	15972
968	15482
969	15332
970	15789
971	16425
972	16252
973	15817
974	15029
975	15218
976	14799
977	13723
978	13386
979	14469
980	13958
981	13341
982	13918
983	14782
984	14454
985	14205
986	12339
987	12463
988	13500
989	13387
990	12932
991	12396
992	11443
993	11572
994	11454
995	11165
996	10782
997	11225
998	12419
999	12126
1000	11686
1001	12188
1002	14245
1003	13368
1004	11110
1005	10446
1006	10156
1007	9656
1008	9478
1009	10738
1010	11675
1011	11741
1012	11100
1013	10093
1014	10340
1015	11232
1016	10779
1017	11412
1018	11434
1019	11022
1020	11148
1021	10682
1022	9941
1023	10548
1024	12172