1	4965
2	5186
3	5180
4	5080
5	4971
6	4978
7	4963
8	4663
9	4703
10	4777
11	5181
12	5627
13	5937
14	5964
15	6052
16	5939
17	5529
18	5352
19	4883
20	4857
21	5056
22	5238
23	5805
24	5787
25	5827
26	5613
27	5425
28	5420
29	5137
30	5083
31	5348
32	5509
33	5503
34	5828
35	6056
36	5875
37	5529
38	4931
39	5079
40	5380
41	5640
42	5878
43	5826
44	5808
45	6086
46	6298
47	6149
48	5933
49	5654
50	5375
51	5572
52	5463
53	5804
54	6099
55	6006
56	5964
57	6269
58	6468
59	6349
60	6463
61	6349
62	6263
63	6220
64	6304
65	6722
66	7119
67	7419
68	7630
69	7330
70	7491
71	7476
72	7432
73	7539
74	7642
75	7843
76	7999
77	7966
78	8101
79	8323
80	8515
81	8648
82	8908
83	9201
84	9533
85	10143
86	10555
87	11026
88	11447
89	11915
90	12394
91	12982
92	13017
93	13220
94	13715
95	14249
96	14975
97	15268
98	15820
99	16728
100	17794
101	18787
102	19871
103	21091
104	21884
105	22824
106	24011
107	25263
108	26857
109	27913
110	29976
111	31970
112	34643
113	37571
114	40572
115	43768
116	46701
117	49707
118	51711
119	52906
120	53824
121	54901
122	54587
123	53488
124	51991
125	50202
126	47337
127	43967
128	40530
129	37826
130	35878
131	33306
132	30915
133	28631
134	26573
135	25292
136	23597
137	21776
138	20114
139	18323
140	17499
141	16906
142	16599
143	16214
144	15594
145	14945
146	14322
147	13820
148	13511
149	13570
150	13313
151	12919
152	11952
153	11072
154	10597
155	10401
156	10318
157	10404
158	10778
159	10485
160	10326
161	10080
162	10123
163	9908
164	9472
165	9223
166	9359
167	9336
168	9733
169	9743
170	9433
171	8793
172	8392
173	8172
174	7794
175	7502
176	7567
177	7694
178	7650
179	7772
180	7665
181	7159
182	6954
183	6773
184	6926
185	6786
186	6568
187	6182
188	6279
189	6554
190	6604
191	6673
192	6778
193	7004
194	6770
195	6298
196	5772
197	5730
198	5830
199	6153
200	6364
201	6783
202	6563
203	6747
204	6920
205	6983
206	6896
207	6664
208	6706
209	6443
210	6406
211	6153
212	6155
213	6025
214	6346
215	6451
216	6410
217	6371
218	6207
219	6090
220	5890
221	5727
222	5763
223	5931
224	6135
225	6379
226	6211
227	6166
228	6206
229	5979
230	5834
231	5611
232	5651
233	5889
234	5812
235	5868
236	5872
237	6009
238	6162
239	6001
240	6114
241	6171
242	6565
243	6618
244	6464
245	6219
246	6052
247	5909
248	5940
249	6110
250	6171
251	5999
252	5867
253	5820
254	6174
255	6432
256	6588
257	6502
258	6550
259	6685
260	6663
261	6321
262	6103
263	6190
264	6474
265	6384
266	6363
267	6010
268	6238
269	6610
270	6642
271	6724
272	7046
273	7346
274	7451
275	7389
276	7128
277	6859
278	7015
279	7056
280	7236
281	7194
282	7439
283	7385
284	7698
285	7848
286	7613
287	7980
288	8252
289	8375
290	8345
291	8313
292	8509
293	8603
294	8732
295	8971
296	9374
297	9734
298	9865
299	10294
300	10344
301	10674
302	10976
303	11632
304	11633
305	11270
306	10974
307	11177
308	12169
309	13028
310	13428
311	13921
312	14647
313	15354
314	15676
315	15556
316	15424
317	15937
318	16622
319	17427
320	17954
321	19132
322	20332
323	20839
324	20804
325	20781
326	20939
327	20933
328	20728
329	20720
330	20624
331	20141
332	18925
333	17995
334	17277
335	17136
336	16864
337	16422
338	16439
339	16305
340	15856
341	15722
342	16220
343	16215
344	15662
345	15172
346	15117
347	16047
348	16582
349	15885
350	15162
351	15152
352	15835
353	16681
354	16992
355	16242
356	15234
357	14685
358	14366
359	13767
360	13250
361	13210
362	13800
363	13921
364	13587
365	13253
366	13224
367	13321
368	13789
369	13677
370	12888
371	12204
372	11548
373	11742
374	12282
375	12223
376	11646
377	11700
378	12061
379	11664
380	11283
381	10888
382	10213
383	9878
384	10140
385	10453
386	10598
387	11153
388	12031
389	12306
390	12191
391	12672
392	13523
393	13979
394	14022
395	14206
396	14593
397	14391
398	13737
399	12968
400	12900
401	13531
402	14265
403	15638
404	16777
405	17760
406	18252
407	17818
408	18150
409	18776
410	19244
411	19662
412	20300
413	21094
414	21634
415	22712
416	24756
417	26666
418	27145
419	27859
420	28554
421	28403
422	28525
423	29312
424	29273
425	27907
426	27419
427	27617
428	27821
429	27508
430	27682
431	27297
432	26754
433	26935
434	26243
435	25038
436	24489
437	24164
438	24162
439	24272
440	23924
441	22620
442	22411
443	22759
444	22555
445	22226
446	22847
447	23982
448	25012
449	25263
450	25743
451	26369
452	27411
453	27744
454	28092
455	28206
456	28884
457	30661
458	33228
459	35451
460	36917
461	37975
462	38838
463	40081
464	42151
465	44143
466	45649
467	47181
468	48298
469	50995
470	51449
471	52744
472	54337
473	57863
474	59975
475	61981
476	65039
477	68978
478	71388
479	71461
480	70370
481	70373
482	72415
483	75290
484	76535
485	77245
486	77435
487	75607
488	73760
489	71393
490	68409
491	66541
492	66082
493	69075
494	70534
495	70927
496	70838
497	69755
498	70335
499	70509
500	71761
501	72729
502	73492
503	75725
504	78639
505	81929
506	84982
507	88362
508	93209
509	98187
510	103595
511	108447
512	113665
513	118465
514	120916
515	124689
516	129236
517	132266
518	135721
519	138939
520	143941
521	143880
522	145535
523	148791
524	153476
525	157769
526	160245
527	161908
528	166338
529	176112
530	183405
531	190355
532	196322
533	204750
534	216975
535	231779
536	243978
537	249435
538	253112
539	253249
540	257809
541	264661
542	267518
543	262737
544	256775
545	252473
546	243543
547	230247
548	218184
549	206471
550	202080
551	201051
552	194723
553	182994
554	172405
555	163806
556	161601
557	165184
558	166158
559	164807
560	163600
561	161458
562	160879
563	161962
564	170852
565	178783
566	182574
567	187985
568	196160
569	200425
570	206415
571	215700
572	223384
573	232975
574	244558
575	258698
576	264244
577	267565
578	272419
579	279710
580	284962
581	284869
582	280551
583	275382
584	262868
585	247673
586	233725
587	223814
588	213013
589	200000
590	186757
591	175830
592	165468
593	157196
594	149063
595	140256
596	132564
597	120886
598	113557
599	108348
600	101162
601	95778
602	90567
603	88175
604	83558
605	79027
606	74735
607	70867
608	66834
609	64762
610	64150
611	61457
612	58148
613	55612
614	53919
615	51988
616	49306
617	47841
618	46365
619	45386
620	44524
621	44606
622	44808
623	44497
624	43880
625	42574
626	41073
627	41017
628	42472
629	41618
630	40544
631	39107
632	38446
633	39864
634	40686
635	41090
636	42571
637	44146
638	42808
639	41884
640	42060
641	44708
642	47476
643	49710
644	49503
645	50596
646	50358
647	49877
648	52979
649	56781
650	58435
651	58797
652	59360
653	60584
654	59678
655	59966
656	58693
657	57507
658	55650
659	53211
660	51355
661	50245
662	48731
663	46192
664	44325
665	42771
666	41726
667	39919
668	37737
669	36925
670	37761
671	37374
672	35040
673	31925
674	30701
675	30207
676	29257
677	26749
678	26541
679	27678
680	27286
681	26638
682	26260
683	26420
684	26003
685	25927
686	25649
687	24363
688	24414
689	25157
690	26244
691	26109
692	24250
693	22113
694	20805
695	20729
696	20509
697	19920
698	20036
699	19364
700	18531
701	17810
702	18894
703	19474
704	19170
705	19020
706	18804
707	18115
708	17949
709	17316
710	16620
711	16888
712	17418
713	18161
714	17695
715	17477
716	18271
717	18600
718	19737
719	21798
720	21832
721	21093
722	20607
723	19809
724	20190
725	20741
726	21937
727	22426
728	21948
729	21698
730	21292
731	21645
732	22343
733	21014
734	19152
735	19699
736	20423
737	19663
738	18181
739	18163
740	18226
741	17084
742	15581
743	13803
744	12402
745	11963
746	12999
747	14032
748	13648
749	12292
750	11441
751	11498
752	11866
753	11909
754	10445
755	9691
756	9121
757	9516
758	10499
759	9836
760	8767
761	8727
762	9286
763	9994
764	9820
765	9950
766	9480
767	8864
768	8355
769	7948
770	8479
771	9111
772	9221
773	8741
774	7865
775	8311
776	7955
777	8083
778	8301
779	8100
780	7915
781	7064
782	6914
783	7401
784	7360
785	7415
786	7570
787	7001
788	6805
789	7261
790	7110
791	6977
792	6808
793	6774
794	6609
795	7013
796	7356
797	7258
798	6874
799	7517
800	7708
801	8045
802	7279
803	5952
804	5637
805	6277
806	6792
807	6932
808	6678
809	6748
810	6722
811	6148
812	5955
813	5859
814	6594
815	6994
816	7054
817	6620
818	6341
819	5958
820	6285
821	6886
822	6658
823	6157
824	5764
825	5836
826	6491
827	6666
828	6804
829	6573
830	6331
831	6356
832	6008
833	5824
834	5687
835	5184
836	4643
837	4973
838	5328
839	5247
840	5643
841	5784
842	5463
843	5417
844	5569
845	5296
846	5187
847	5197
848	5417
849	5700
850	5544
851	5024
852	5461
853	5872
854	6042
855	5713
856	5916
857	5590
858	5307
859	5783
860	5994
861	5731
862	5685
863	6063
864	5578
865	4968
866	4681
867	4964
868	5830
869	6169
870	5791
871	5368
872	5389
873	5965
874	5858
875	5464
876	5948
877	6329
878	5922
879	5746
880	5971
881	5650
882	5804
883	5390
884	5977
885	6513
886	6339
887	5693
888	5691
889	5211
890	4790
891	4421
892	4493
893	4456
894	4116
895	4325
896	5119
897	5648
898	5011
899	5372
900	6145
901	6535
902	5700
903	5001
904	4951
905	5245
906	5151
907	4905
908	4607
909	4524
910	4672
911	4507
912	4521
913	5297
914	5598
915	5171
916	5012
917	4895
918	4444
919	4622
920	4870
921	5097
922	4986
923	4986
924	4676
925	4482
926	5233
927	4904
928	4218
929	4291
930	5319
931	5138
932	4945
933	5144
934	5128
935	5179
936	4860
937	5170
938	5133
939	5728
940	5849
941	5833
942	5474
943	4520
944	4729
945	4854
946	5161
947	5564
948	5281
949	5197
950	5673
951	5684
952	5484
953	5259
954	5005
955	4823
956	4943
957	4942
958	5206
959	4909
960	4613
961	4836
962	5442
963	5565
964	4967
965	4694
966	4559
967	5051
968	5602
969	5523
970	5352
971	5885
972	5421
973	5765
974	6374
975	6154
976	5145
977	4355
978	4200
979	4541
980	4709
981	5090
982	5229
983	4692
984	4688
985	4675
986	4522
987	5743
988	6096
989	5592
990	5485
991	5207
992	4394
993	5232
994	5972
995	5679
996	5659
997	5788
998	5893
999	4949
1000	4651
1001	4826
1002	5037
1003	5426
1004	5173
1005	5178
1006	5832
1007	5272
1008	5038
1009	4772
1010	4833
1011	4789
1012	4908
1013	5250
1014	4407
1015	4110
1016	4452
1017	4601
1018	4198
1019	4391
1020	4962
1021	4933
1022	5240
1023	5382
1024	5728