1	8571
2	8105
3	7883
4	7861
5	7914
6	7659
7	7931
8	8052
9	8319
10	8281
11	8867
12	8129
13	8298
14	8615
15	8619
16	9188
17	8838
18	8458
19	8743
20	8621
21	8820
22	8575
23	8589
24	8297
25	8205
26	7874
27	8095
28	7566
29	7577
30	7625
31	7811
32	8508
33	9110
34	8843
35	8873
36	8604
37	9362
38	9399
39	10118
40	10398
41	10857
42	10360
43	9321
44	9215
45	9458
46	9141
47	8614
48	8527
49	8778
50	8464
51	8114
52	8144
53	8250
54	9480
55	10259
56	10694
57	11082
58	11008
59	11361
60	10861
61	10429
62	9444
63	9288
64	8862
65	8186
66	8211
67	7850
68	8165
69	7858
70	8327
71	8557
72	8243
73	8419
74	9128
75	9537
76	9686
77	10355
78	9575
79	9389
80	8753
81	8667
82	8299
83	8271
84	8155
85	8531
86	9274
87	9316
88	9352
89	9245
90	9808
91	9990
92	10357
93	10718
94	10543
95	11058
96	11005
97	10544
98	10669
99	10742
100	10909
101	11261
102	11841
103	12631
104	13346
105	13804
106	14471
107	15205
108	15400
109	16266
110	17968
111	19997
112	22201
113	23958
114	25651
115	26908
116	28573
117	29766
118	29403
119	29919
120	29388
121	29934
122	30018
123	28691
124	27340
125	25563
126	23269
127	20319
128	18376
129	16611
130	16256
131	15560
132	15275
133	14521
134	13645
135	13414
136	13356
137	13217
138	12039
139	11568
140	10705
141	10856
142	11387
143	11680
144	11319
145	11263
146	10900
147	10399
148	10521
149	10518
150	10458
151	10151
152	10138
153	9006
154	9198
155	9002
156	9272
157	9190
158	9028
159	8933
160	9208
161	9173
162	9616
163	9590
164	10654
165	9941
166	9664
167	8820
168	8160
169	7877
170	7500
171	7676
172	7593
173	7899
174	8416
175	8450
176	8770
177	9131
178	9416
179	9075
180	9141
181	8358
182	8734
183	8172
184	8226
185	7947
186	7860
187	8081
188	7753
189	8199
190	7738
191	8128
192	8235
193	8839
194	8672
195	9011
196	9413
197	9555
198	8689
199	8313
200	8006
201	7652
202	7163
203	7053
204	7460
205	8039
206	8569
207	8200
208	8275
209	7629
210	7633
211	8064
212	8897
213	8767
214	8498
215	8439
216	7781
217	7880
218	7818
219	7987
220	8516
221	9008
222	8844
223	8608
224	8210
225	7704
226	7841
227	8190
228	8458
229	8098
230	8081
231	8572
232	9068
233	9051
234	9009
235	8966
236	9158
237	8813
238	8152
239	7411
240	7748
241	8030
242	8182
243	8169
244	8161
245	8643
246	8718
247	8673
248	8439
249	8093
250	8438
251	8446
252	8704
253	8344
254	7763
255	7619
256	7417
257	7890
258	8144
259	8517
260	8695
261	8596
262	7929
263	7952
264	8695
265	8508
266	8226
267	8083
268	8427
269	9002
270	8878
271	8955
272	8629
273	8965
274	8834
275	8816
276	8818
277	8939
278	9132
279	8550
280	8545
281	8158
282	8824
283	8459
284	8740
285	8951
286	8770
287	8711
288	8519
289	8456
290	8677
291	8987
292	8337
293	8316
294	8179
295	8053
296	8296
297	8627
298	8649
299	9224
300	9496
301	9343
302	9641
303	9891
304	10680
305	10209
306	9865
307	9772
308	8781
309	8795
310	8547
311	8478
312	8749
313	9179
314	9258
315	9614
316	10502
317	11923
318	12219
319	12004
320	11544
321	11446
322	11947
323	12385
324	12781
325	13385
326	13774
327	13480
328	12640
329	12946
330	13440
331	13312
332	12521
333	12287
334	11622
335	11390
336	11402
337	11489
338	11410
339	11191
340	10680
341	11300
342	10905
343	11315
344	10952
345	11131
346	11752
347	12552
348	12374
349	11739
350	11498
351	10846
352	10456
353	10905
354	10862
355	10847
356	10714
357	9723
358	10021
359	10292
360	10909
361	10355
362	9429
363	8960
364	8463
365	8526
366	8995
367	8949
368	8391
369	8276
370	8314
371	8370
372	8876
373	8778
374	9093
375	9144
376	8773
377	8227
378	8339
379	8221
380	8673
381	9004
382	8711
383	8909
384	9326
385	9153
386	8518
387	7843
388	7592
389	7760
390	8180
391	8046
392	8690
393	9523
394	9762
395	9546
396	8816
397	8511
398	9148
399	10088
400	10246
401	10599
402	10279
403	10043
404	9490
405	9803
406	10254
407	10592
408	10396
409	10418
410	11122
411	11473
412	12175
413	12414
414	12276
415	13021
416	13778
417	14716
418	15194
419	14917
420	14241
421	14220
422	13992
423	13601
424	13482
425	13398
426	14041
427	14629
428	14189
429	13319
430	12722
431	12122
432	11129
433	10618
434	10740
435	10568
436	10141
437	9540
438	10090
439	10660
440	9951
441	9532
442	10049
443	10601
444	11445
445	11953
446	11294
447	10720
448	10526
449	11674
450	11237
451	10572
452	10152
453	10703
454	10913
455	10871
456	11205
457	11212
458	12398
459	13885
460	14068
461	14606
462	14517
463	14108
464	14244
465	15258
466	15858
467	17267
468	17449
469	18451
470	18008
471	18274
472	18625
473	19549
474	20179
475	21495
476	22630
477	23978
478	24330
479	25294
480	27274
481	29041
482	31110
483	32093
484	31247
485	29811
486	28804
487	27760
488	26520
489	25174
490	23952
491	22808
492	22016
493	22225
494	22234
495	22816
496	23502
497	23085
498	21566
499	20548
500	20918
501	21462
502	21744
503	22631
504	24303
505	26764
506	28342
507	28747
508	29698
509	31974
510	34129
511	35418
512	36025
513	37981
514	39792
515	41621
516	43657
517	45159
518	47104
519	46890
520	46163
521	45906
522	46601
523	45831
524	44305
525	43102
526	44192
527	47370
528	49753
529	52527
530	54018
531	56423
532	59530
533	64077
534	68672
535	75884
536	83781
537	88874
538	92813
539	93474
540	94987
541	99418
542	100030
543	94355
544	88642
545	84892
546	80982
547	76295
548	69100
549	62235
550	57333
551	54665
552	51457
553	48988
554	47381
555	45730
556	43002
557	41059
558	40881
559	40990
560	42069
561	42058
562	42714
563	44250
564	47539
565	49841
566	52407
567	55546
568	59471
569	59667
570	62839
571	66650
572	71562
573	76108
574	80899
575	87251
576	91820
577	95007
578	98811
579	101654
580	103642
581	100151
582	98018
583	94993
584	89292
585	85419
586	81106
587	76409
588	69855
589	64125
590	59184
591	54481
592	49292
593	43307
594	39849
595	37044
596	35071
597	32194
598	29532
599	28201
600	26677
601	24440
602	22988
603	21525
604	20178
605	19991
606	20532
607	20367
608	20236
609	18911
610	17478
611	16700
612	16168
613	16815
614	16769
615	17251
616	17740
617	17634
618	17599
619	18206
620	18445
621	18372
622	17815
623	16654
624	14751
625	14286
626	13811
627	13911
628	13723
629	13711
630	13955
631	13881
632	13093
633	13539
634	14151
635	14637
636	14722
637	15287
638	15109
639	15860
640	16456
641	16235
642	15797
643	16893
644	18438
645	19775
646	20089
647	21264
648	23517
649	23834
650	23168
651	23495
652	25350
653	25280
654	24473
655	23656
656	22621
657	20861
658	20493
659	19976
660	18541
661	17294
662	17150
663	17084
664	15963
665	15009
666	15837
667	16100
668	15562
669	15040
670	14612
671	12516
672	12158
673	12801
674	12978
675	12525
676	12991
677	12552
678	11636
679	11432
680	12831
681	13816
682	12623
683	11125
684	11741
685	12602
686	11227
687	10453
688	10465
689	10447
690	10566
691	10547
692	10312
693	9846
694	9732
695	9477
696	10603
697	10032
698	9178
699	8751
700	8600
701	9194
702	9512
703	9131
704	9387
705	10999
706	11302
707	10716
708	9700
709	9447
710	9820
711	10571
712	11875
713	11139
714	10592
715	9712
716	10022
717	11296
718	12358
719	12253
720	11963
721	11898
722	12017
723	12044
724	12047
725	12400
726	12971
727	12704
728	12536
729	12839
730	14092
731	15775
732	15706
733	15727
734	15959
735	16534
736	16810
737	18013
738	17745
739	15827
740	14514
741	12961
742	12264
743	11488
744	10873
745	10037
746	10327
747	10424
748	10661
749	9734
750	9133
751	9280
752	9047
753	8630
754	8384
755	8011
756	8569
757	8315
758	7594
759	7764
760	8035
761	7997
762	8218
763	7461
764	7878
765	8112
766	8802
767	9541
768	9477
769	9502
770	10403
771	10108
772	9708
773	10111
774	10809
775	10434
776	9456
777	8850
778	8216
779	7911
780	8085
781	9485
782	9697
783	8405
784	8491
785	8498
786	8504
787	9023
788	9382
789	9660
790	9211
791	8503
792	7409
793	8299
794	8235
795	8778
796	7930
797	7693
798	7552
799	8093
800	7411
801	7594
802	7757
803	8181
804	8237
805	7356
806	8572
807	8628
808	8821
809	9916
810	9760
811	9812
812	10099
813	10273
814	10403
815	10275
816	10004
817	8527
818	7878
819	7807
820	7464
821	7949
822	9045
823	8903
824	8828
825	8632
826	8099
827	9287
828	8939
829	7734
830	6986
831	7903
832	7995
833	8175
834	8209
835	8752
836	8244
837	8596
838	8182
839	7660
840	7931
841	8499
842	7815
843	6783
844	7364
845	8159
846	8232
847	8540
848	8224
849	6963
850	6631
851	7894
852	8172
853	8063
854	7825
855	7371
856	7343
857	8289
858	8781
859	8834
860	8093
861	8514
862	9423
863	7833
864	6924
865	7959
866	8452
867	9042
868	9204
869	8160
870	7497
871	8755
872	8938
873	9457
874	8998
875	8389
876	8464
877	8178
878	8285
879	8488
880	8890
881	9423
882	9145
883	9041
884	8854
885	9195
886	9188
887	8756
888	7708
889	7089
890	8177
891	8959
892	8404
893	8905
894	7865
895	7996
896	8437
897	7063
898	7619
899	8540
900	7900
901	6785
902	7161
903	8001
904	8957
905	9266
906	8502
907	8289
908	8107
909	8454
910	9284
911	8865
912	9081
913	8906
914	8646
915	8483
916	8459
917	7942
918	8131
919	9341
920	9562
921	8771
922	8639
923	8370
924	9624
925	9263
926	9519
927	9785
928	9649
929	8184
930	7946
931	8049
932	7888
933	8192
934	8168
935	7305
936	7286
937	7686
938	7672
939	7202
940	6326
941	7117
942	7997
943	7948
944	9064
945	8836
946	8319
947	9407
948	8253
949	8137
950	7717
951	8137
952	8009
953	7363
954	7947
955	7553
956	9481
957	10040
958	7754
959	7547
960	7595
961	9057
962	9872
963	10082
964	9550
965	8833
966	10261
967	10558
968	9986
969	8651
970	7780
971	8072
972	8417
973	8622
974	7550
975	6861
976	7690
977	7939
978	7946
979	7437
980	7026
981	7320
982	7388
983	8142
984	8380
985	7587
986	8004
987	8424
988	8466
989	9570
990	9475
991	9586
992	9608
993	8758
994	7735
995	8162
996	9330
997	8834
998	8536
999	8028
1000	6420
1001	6861
1002	8210
1003	8450
1004	8264
1005	8153
1006	8128
1007	9309
1008	10626
1009	9412
1010	8734
1011	10411
1012	10123
1013	9685
1014	9197
1015	8356
1016	8127
1017	9227
1018	8978
1019	10318
1020	10155
1021	9776
1022	9357
1023	8549
1024	8826