1	6919
2	7203
3	7090
4	7090
5	7146
6	7108
7	7357
8	7383
9	7355
10	7169
11	7177
12	7252
13	7405
14	7214
15	7344
16	7064
17	7147
18	7211
19	7048
20	7010
21	7054
22	7133
23	7319
24	7446
25	7849
26	7760
27	7635
28	7092
29	6645
30	6707
31	6843
32	6907
33	7154
34	7623
35	8140
36	8704
37	9035
38	9025
39	9109
40	8881
41	8699
42	8789
43	9002
44	9534
45	9954
46	9947
47	9535
48	9155
49	8958
50	9255
51	9726
52	9718
53	9559
54	8913
55	8548
56	8856
57	9389
58	9614
59	9640
60	9550
61	9551
62	9592
63	10132
64	10472
65	10991
66	11325
67	11224
68	11128
69	10592
70	10422
71	10779
72	10825
73	10677
74	10761
75	11181
76	11810
77	12064
78	12709
79	13191
80	13263
81	13312
82	13263
83	13498
84	13929
85	14120
86	14359
87	14573
88	15104
89	15464
90	16215
91	16921
92	17346
93	17831
94	18386
95	18862
96	19741
97	20532
98	21245
99	21762
100	22329
101	22852
102	24396
103	25964
104	27498
105	28844
106	29913
107	31454
108	33043
109	35265
110	37455
111	39361
112	41359
113	43006
114	45207
115	47374
116	50003
117	51959
118	53100
119	53613
120	54688
121	55856
122	56348
123	55580
124	54003
125	52776
126	50969
127	48619
128	46551
129	44542
130	42984
131	40592
132	37987
133	35565
134	33474
135	32535
136	30626
137	29039
138	26964
139	25407
140	24912
141	23842
142	22893
143	21929
144	21350
145	20860
146	20099
147	19134
148	18967
149	18473
150	17906
151	17170
152	16056
153	15761
154	15511
155	14918
156	14632
157	14748
158	14871
159	14970
160	15062
161	14787
162	14728
163	14197
164	13598
165	13332
166	13650
167	14178
168	13974
169	13331
170	12383
171	11777
172	11388
173	11059
174	10718
175	10232
176	10014
177	10381
178	10639
179	10753
180	10868
181	10412
182	10261
183	10128
184	9731
185	9530
186	9400
187	9335
188	9611
189	10013
190	10172
191	9937
192	9514
193	9441
194	9244
195	9490
196	9451
197	9381
198	9527
199	9840
200	9884
201	9677
202	9128
203	8787
204	8677
205	8704
206	8780
207	8962
208	9242
209	9491
210	9892
211	9529
212	9310
213	9174
214	9298
215	9104
216	9009
217	9237
218	9434
219	9598
220	9401
221	9076
222	9007
223	9187
224	9600
225	9481
226	9228
227	9017
228	8881
229	8891
230	9005
231	9146
232	9035
233	8865
234	8539
235	8573
236	9200
237	9467
238	9695
239	9294
240	9019
241	8740
242	8832
243	8727
244	8385
245	8134
246	8363
247	8941
248	9275
249	9559
250	9624
251	9883
252	9964
253	9432
254	9092
255	8991
256	9400
257	9576
258	9585
259	9720
260	9257
261	8810
262	8606
263	8484
264	8338
265	8451
266	8747
267	9118
268	9749
269	10066
270	9988
271	9427
272	9171
273	9196
274	9434
275	9889
276	9732
277	9676
278	10014
279	10342
280	10548
281	10524
282	10253
283	10250
284	10557
285	11148
286	11508
287	11484
288	11370
289	11797
290	12152
291	12586
292	12874
293	12881
294	12877
295	13079
296	13533
297	13836
298	14061
299	14458
300	14708
301	15505
302	16250
303	16719
304	16750
305	16546
306	16547
307	17338
308	18112
309	18791
310	18972
311	18936
312	19511
313	20199
314	20828
315	20887
316	21068
317	21622
318	21691
319	22456
320	23296
321	25035
322	26308
323	27393
324	27120
325	26849
326	26413
327	26804
328	26800
329	26898
330	27046
331	26733
332	25705
333	25288
334	24476
335	23672
336	22847
337	21930
338	21944
339	22408
340	22743
341	23194
342	22852
343	21287
344	21067
345	21657
346	22847
347	24041
348	24523
349	23847
350	22784
351	22223
352	22091
353	22265
354	22479
355	22250
356	22158
357	22194
358	22104
359	21649
360	22027
361	21624
362	21304
363	20751
364	20892
365	20545
366	19630
367	18591
368	17906
369	18159
370	18560
371	18417
372	17496
373	16909
374	16821
375	17299
376	17353
377	17042
378	16777
379	16343
380	16368
381	16347
382	16390
383	16223
384	16367
385	17095
386	17462
387	17516
388	17540
389	17306
390	17209
391	17281
392	17180
393	17813
394	19186
395	20365
396	20446
397	20008
398	20117
399	20624
400	21546
401	22473
402	23117
403	23811
404	23970
405	24207
406	24887
407	25196
408	25562
409	25950
410	27234
411	28577
412	30124
413	31301
414	31785
415	31533
416	31187
417	31916
418	32851
419	33531
420	34941
421	35960
422	36646
423	37107
424	37668
425	38013
426	37243
427	36149
428	35947
429	35804
430	35538
431	34543
432	33917
433	33263
434	32470
435	32593
436	32724
437	32681
438	32376
439	31198
440	30712
441	29954
442	30262
443	30962
444	31585
445	33373
446	35755
447	36419
448	36245
449	35614
450	35522
451	36582
452	38090
453	37577
454	37872
455	37455
456	37279
457	38308
458	41474
459	45130
460	48041
461	50640
462	52274
463	54639
464	56781
465	58723
466	61123
467	62987
468	64530
469	67150
470	68108
471	70559
472	71989
473	75013
474	76562
475	78007
476	79146
477	80206
478	82503
479	85893
480	91011
481	95876
482	97758
483	97217
484	97047
485	97603
486	98658
487	98661
488	98237
489	96240
490	95203
491	95077
492	95256
493	97475
494	98876
495	99720
496	99896
497	98426
498	99481
499	100510
500	100931
501	102294
502	105291
503	109839
504	113074
505	114973
506	116909
507	119396
508	125670
509	130098
510	132857
511	135349
512	139965
513	146796
514	151554
515	154491
516	158436
517	164445
518	170279
519	172603
520	174652
521	175714
522	182133
523	188392
524	195028
525	201025
526	204824
527	209616
528	214380
529	220204
530	227774
531	235949
532	243986
533	252766
534	258365
535	263461
536	274696
537	286006
538	297069
539	302587
540	305297
541	311522
542	312524
543	308376
544	304812
545	302987
546	292474
547	277442
548	263995
549	251516
550	248429
551	247426
552	244189
553	237333
554	230894
555	225433
556	222105
557	223097
558	221280
559	217682
560	217695
561	216479
562	218006
563	222132
564	233740
565	242320
566	244758
567	247241
568	254335
569	260792
570	268676
571	276855
572	285345
573	292981
574	296523
575	306420
576	311165
577	313674
578	317247
579	319228
580	320595
581	316988
582	313224
583	307113
584	295312
585	285909
586	275163
587	267542
588	257523
589	245998
590	230779
591	218756
592	208377
593	196519
594	185878
595	174951
596	168118
597	158069
598	148557
599	142341
600	136286
601	128681
602	119894
603	117607
604	115433
605	111369
606	106539
607	102657
608	98507
609	95136
610	93255
611	88931
612	83465
613	81805
614	79911
615	76822
616	73566
617	73550
618	72920
619	71281
620	69557
621	67295
622	65046
623	63146
624	61944
625	62632
626	63193
627	63132
628	62224
629	60893
630	62010
631	61665
632	58866
633	59036
634	60683
635	60878
636	59618
637	58389
638	57025
639	57332
640	58934
641	61151
642	62995
643	64782
644	64899
645	66765
646	68246
647	68509
648	68430
649	68090
650	69587
651	71321
652	73599
653	74865
654	73910
655	72132
656	70470
657	69339
658	67113
659	63824
660	63490
661	64460
662	63088
663	59271
664	57332
665	56089
666	55362
667	54422
668	52482
669	50793
670	49100
671	49210
672	49460
673	47970
674	45374
675	43122
676	41103
677	38057
678	36027
679	36860
680	37980
681	37225
682	35656
683	35637
684	36587
685	35760
686	34944
687	35798
688	36389
689	36031
690	36610
691	34822
692	32661
693	31423
694	30638
695	31099
696	31808
697	30476
698	29157
699	28003
700	27751
701	27552
702	27410
703	26334
704	25127
705	25191
706	26192
707	26288
708	26297
709	25530
710	24571
711	25788
712	25899
713	24798
714	24501
715	25243
716	25407
717	24969
718	24368
719	25111
720	25525
721	25276
722	26906
723	27852
724	28215
725	27965
726	28013
727	28632
728	28662
729	27828
730	27102
731	25824
732	23547
733	22566
734	22942
735	23529
736	22794
737	22661
738	23565
739	23028
740	22427
741	21045
742	21062
743	21178
744	20085
745	18677
746	17981
747	18071
748	19529
749	19579
750	18164
751	17143
752	16056
753	15719
754	16018
755	15984
756	15027
757	14054
758	15022
759	16347
760	15596
761	14806
762	14354
763	13703
764	13366
765	13718
766	13051
767	12453
768	11421
769	10782
770	11433
771	12576
772	13422
773	13322
774	13039
775	12761
776	12013
777	12231
778	12213
779	12432
780	11219
781	10277
782	10927
783	10699
784	11001
785	10183
786	9802
787	10765
788	10569
789	10821
790	10541
791	10253
792	9461
793	9752
794	10666
795	10747
796	10710
797	10979
798	11496
799	11092
800	10616
801	9797
802	9468
803	9711
804	9873
805	10029
806	9808
807	9515
808	8911
809	9132
810	9084
811	8655
812	9710
813	9058
814	8555
815	8933
816	9329
817	10088
818	9927
819	9284
820	9344
821	9816
822	10605
823	10530
824	9951
825	9441
826	9113
827	8745
828	8385
829	8608
830	8795
831	9410
832	9854
833	9449
834	8381
835	8812
836	9577
837	9737
838	8688
839	8681
840	9584
841	9423
842	8567
843	8793
844	8088
845	7074
846	7454
847	8244
848	8145
849	8390
850	7711
851	7798
852	7969
853	7820
854	8510
855	8262
856	8305
857	8198
858	8457
859	8610
860	8239
861	7441
862	8177
863	8513
864	8330
865	8738
866	8061
867	7805
868	8945
869	9338
870	8605
871	8371
872	8305
873	8160
874	8913
875	8912
876	8190
877	7623
878	7570
879	8375
880	8269
881	8154
882	8774
883	9282
884	9322
885	8678
886	7882
887	7183
888	7281
889	7388
890	7769
891	7488
892	7511
893	8314
894	8422
895	7224
896	7320
897	7674
898	8175
899	7846
900	7581
901	7073
902	7114
903	7295
904	7324
905	7240
906	6913
907	7056
908	8000
909	7749
910	7018
911	6390
912	6668
913	6747
914	7024
915	8076
916	8745
917	8974
918	8714
919	8107
920	8122
921	8437
922	8398
923	7257
924	7217
925	7207
926	7459
927	8541
928	8644
929	7604
930	7678
931	7833
932	7424
933	6410
934	6447
935	6805
936	7610
937	7368
938	6843
939	6427
940	6810
941	7264
942	7527
943	7324
944	7324
945	7448
946	7250
947	7543
948	7196
949	6921
950	7470
951	7949
952	7875
953	7869
954	7565
955	7316
956	6978
957	6850
958	7596
959	6942
960	6447
961	5718
962	5644
963	5766
964	6555
965	8063
966	8402
967	7579
968	7311
969	6138
970	6042
971	6774
972	7564
973	8154
974	8400
975	8547
976	7662
977	6961
978	6410
979	6707
980	7204
981	7154
982	6905
983	7153
984	7783
985	8315
986	6834
987	7365
988	8450
989	9091
990	9073
991	7814
992	7467
993	7424
994	6842
995	6841
996	6389
997	6695
998	7494
999	8182
1000	7764
1001	7463
1002	7648
1003	7912
1004	7768
1005	8273
1006	8058
1007	7909
1008	7901
1009	7167
1010	6733
1011	6579
1012	6805
1013	6675
1014	7180
1015	7831
1016	7117
1017	7100
1018	8073
1019	8654
1020	8099
1021	7262
1022	7107
1023	7131
1024	7337