1	3677
2	3895
3	3814
4	3604
5	3546
6	3678
7	3813
8	3741
9	3804
10	3564
11	3481
12	3346
13	3144
14	3153
15	3244
16	3298
17	3379
18	3705
19	3611
20	3572
21	3207
22	2884
23	3051
24	3044
25	3194
26	3147
27	3347
28	3738
29	3826
30	4015
31	3845
32	3863
33	3778
34	3678
35	3919
36	3763
37	3636
38	3481
39	3429
40	3557
41	3517
42	3391
43	3558
44	3853
45	4441
46	4682
47	4622
48	4435
49	4072
50	3746
51	3719
52	3494
53	3780
54	3818
55	3708
56	3524
57	3701
58	3869
59	4050
60	4358
61	4607
62	4782
63	4801
64	4628
65	4689
66	4570
67	4200
68	4113
69	4075
70	4247
71	4527
72	4698
73	4890
74	4975
75	5291
76	5595
77	5530
78	5879
79	5997
80	6203
81	6196
82	6106
83	6128
84	6033
85	6393
86	6335
87	6167
88	5988
89	6053
90	6420
91	6585
92	6602
93	6842
94	7274
95	7572
96	7921
97	8001
98	8333
99	8891
100	9527
101	10216
102	10664
103	11359
104	11879
105	12554
106	13589
107	14655
108	16041
109	17243
110	20002
111	22982
112	26371
113	29645
114	32638
115	35019
116	36903
117	38996
118	39962
119	40769
120	41462
121	42595
122	41686
123	40206
124	38009
125	36303
126	34174
127	31207
128	28053
129	25357
130	23367
131	21372
132	19403
133	17569
134	15790
135	14242
136	13110
137	12410
138	11964
139	11071
140	10620
141	10430
142	10370
143	10022
144	9832
145	9759
146	9218
147	8356
148	7913
149	7446
150	7687
151	7805
152	7541
153	7316
154	7131
155	6818
156	6546
157	6203
158	6118
159	6051
160	6272
161	5848
162	6096
163	6036
164	6073
165	5734
166	5540
167	5307
168	5384
169	5633
170	5417
171	5493
172	5085
173	4893
174	4699
175	4655
176	4636
177	4487
178	4026
179	3855
180	3871
181	3966
182	4140
183	4407
184	4543
185	4958
186	4893
187	4911
188	4746
189	4795
190	4933
191	5059
192	4788
193	4402
194	3880
195	3467
196	3489
197	3959
198	4428
199	4451
200	4198
201	3929
202	3891
203	3965
204	4159
205	4140
206	4026
207	4004
208	3928
209	3644
210	3592
211	3348
212	3343
213	3368
214	3684
215	3894
216	4224
217	4584
218	4700
219	4657
220	4163
221	4033
222	4112
223	4005
224	4100
225	3970
226	3958
227	4121
228	4330
229	4446
230	4311
231	4025
232	3392
233	3162
234	3056
235	3464
236	3490
237	3526
238	3379
239	3295
240	3224
241	3472
242	3574
243	3641
244	3707
245	3622
246	3750
247	3875
248	4045
249	4456
250	4581
251	4237
252	4446
253	4318
254	4259
255	4038
256	4122
257	3938
258	3751
259	3578
260	3790
261	3869
262	4000
263	4219
264	4175
265	4129
266	4095
267	4073
268	3895
269	3695
270	3637
271	3826
272	3974
273	4222
274	3965
275	4084
276	4086
277	3903
278	3914
279	4266
280	4773
281	5129
282	5479
283	5668
284	5568
285	5155
286	4890
287	4820
288	4719
289	4589
290	4469
291	4726
292	5420
293	5831
294	6025
295	5900
296	5582
297	5291
298	5487
299	5909
300	6130
301	6038
302	6135
303	6620
304	6839
305	6800
306	6431
307	6574
308	6869
309	7552
310	8018
311	7858
312	8406
313	8759
314	9036
315	9263
316	9504
317	10116
318	10805
319	11283
320	11911
321	12638
322	13260
323	14105
324	15254
325	15734
326	15510
327	15426
328	14624
329	14041
330	13216
331	12559
332	11964
333	11676
334	11079
335	10581
336	9735
337	9393
338	8918
339	9176
340	9305
341	9501
342	9420
343	9403
344	9590
345	9446
346	9317
347	9514
348	9807
349	9815
350	10194
351	10892
352	11635
353	11130
354	10498
355	9220
356	8965
357	9094
358	9045
359	8644
360	8172
361	7449
362	7311
363	7101
364	7063
365	6707
366	6416
367	6067
368	5917
369	5767
370	5891
371	6196
372	6317
373	6436
374	6456
375	6637
376	6742
377	6625
378	6282
379	5913
380	6082
381	6635
382	6952
383	6703
384	6232
385	6234
386	6289
387	6446
388	7297
389	7361
390	7100
391	6881
392	6621
393	6541
394	6584
395	7265
396	7734
397	7624
398	7747
399	8421
400	8412
401	8406
402	8027
403	8059
404	8311
405	8880
406	10109
407	10947
408	11118
409	11187
410	10936
411	11607
412	12085
413	12480
414	12902
415	14560
416	15547
417	16684
418	17448
419	17811
420	17800
421	17694
422	17537
423	18102
424	18905
425	18452
426	18069
427	16955
428	16009
429	15161
430	15104
431	15094
432	14928
433	14650
434	13775
435	13000
436	12391
437	12290
438	11776
439	11927
440	12174
441	11734
442	11233
443	10853
444	11068
445	11096
446	11514
447	11616
448	12164
449	13000
450	13194
451	13147
452	13480
453	13527
454	13726
455	13688
456	14051
457	15012
458	15909
459	16780
460	17061
461	18119
462	19151
463	20822
464	22335
465	23210
466	23792
467	24091
468	25682
469	27926
470	28564
471	29571
472	29831
473	31130
474	33605
475	36192
476	38328
477	39152
478	40102
479	41410
480	43345
481	43918
482	43965
483	45230
484	45901
485	46217
486	46892
487	46315
488	44575
489	42604
490	41781
491	41135
492	40519
493	40142
494	39228
495	38691
496	37562
497	36282
498	36534
499	36911
500	38483
501	40024
502	41100
503	42533
504	44592
505	46430
506	48387
507	50042
508	53765
509	58426
510	62260
511	65345
512	68150
513	71846
514	74023
515	75875
516	76546
517	78205
518	80441
519	83054
520	85041
521	84366
522	84557
523	85605
524	87504
525	89708
526	90582
527	93534
528	97101
529	101915
530	106494
531	111023
532	116881
533	123126
534	130477
535	140435
536	150387
537	156504
538	165812
539	172198
540	174856
541	176785
542	175967
543	171906
544	166626
545	160794
546	153188
547	141930
548	132440
549	125135
550	122328
551	118124
552	111567
553	104786
554	98307
555	92320
556	87987
557	87863
558	88700
559	89845
560	89084
561	86105
562	85560
563	87839
564	91971
565	95239
566	99641
567	105726
568	111941
569	114880
570	120242
571	126222
572	132677
573	140061
574	149739
575	162036
576	168305
577	174845
578	181600
579	190472
580	194906
581	193511
582	189177
583	183406
584	175795
585	166631
586	157183
587	149339
588	137822
589	125454
590	114249
591	106130
592	98022
593	89312
594	82778
595	77629
596	72953
597	66354
598	60830
599	55332
600	51320
601	48445
602	45244
603	43317
604	41635
605	40824
606	39486
607	38035
608	35218
609	33022
610	31309
611	29576
612	28427
613	28370
614	28407
615	28293
616	27236
617	26433
618	25278
619	24061
620	22930
621	22014
622	21240
623	20801
624	20598
625	19720
626	20015
627	20359
628	20276
629	19982
630	20016
631	20584
632	20883
633	20349
634	20345
635	21676
636	23507
637	24823
638	23916
639	22861
640	22307
641	23803
642	24695
643	25392
644	25629
645	28049
646	31606
647	33176
648	33922
649	34196
650	35942
651	37088
652	37740
653	37688
654	37200
655	37767
656	37464
657	36420
658	34764
659	33628
660	32927
661	33174
662	31201
663	28677
664	26455
665	24414
666	23005
667	22114
668	21377
669	20528
670	18513
671	16980
672	16168
673	15793
674	15768
675	15497
676	14984
677	14040
678	14323
679	15149
680	15453
681	15202
682	14893
683	14620
684	15239
685	15338
686	13671
687	12619
688	12252
689	12410
690	12662
691	12339
692	11829
693	11331
694	10494
695	10414
696	10836
697	9993
698	9401
699	9782
700	10176
701	9331
702	8663
703	8936
704	9561
705	9830
706	10505
707	10751
708	10231
709	9404
710	9374
711	9369
712	9806
713	9952
714	9878
715	9864
716	9723
717	9672
718	10315
719	11262
720	12046
721	11757
722	11174
723	11117
724	11783
725	12651
726	13612
727	14627
728	14863
729	14304
730	13944
731	13395
732	13476
733	13935
734	13280
735	12378
736	11290
737	10967
738	10072
739	9101
740	8983
741	9578
742	9555
743	8105
744	7261
745	7414
746	7473
747	7364
748	6836
749	6429
750	6209
751	6100
752	5977
753	5938
754	5560
755	5456
756	5582
757	5274
758	5064
759	5664
760	5458
761	5156
762	4662
763	4756
764	4960
765	5250
766	5244
767	4863
768	5023
769	4893
770	5425
771	5945
772	5673
773	5214
774	5182
775	4933
776	3904
777	3963
778	3994
779	3853
780	4433
781	4758
782	4768
783	4503
784	4507
785	4827
786	4819
787	4880
788	5016
789	5323
790	5231
791	4939
792	5088
793	4712
794	4669
795	4549
796	4511
797	4656
798	3551
799	3391
800	3654
801	3798
802	3719
803	4208
804	4472
805	4274
806	4096
807	3704
808	3730
809	4223
810	4072
811	3548
812	3781
813	4048
814	4157
815	4296
816	4477
817	4755
818	3756
819	2941
820	2818
821	2917
822	3254
823	3970
824	4335
825	4445
826	4180
827	3552
828	3188
829	3431
830	3453
831	3523
832	3436
833	3511
834	3587
835	3755
836	3369
837	3348
838	3298
839	2946
840	2623
841	2728
842	2713
843	2925
844	3310
845	3811
846	3519
847	3223
848	3720
849	3382
850	3383
851	3926
852	4252
853	3984
854	3666
855	3127
856	3296
857	3453
858	3924
859	4105
860	4677
861	4369
862	3953
863	3593
864	3445
865	3421
866	3012
867	3191
868	3642
869	4098
870	3791
871	3581
872	3583
873	3049
874	3339
875	4042
876	4268
877	4288
878	3991
879	3573
880	3268
881	3313
882	3420
883	3464
884	3239
885	2964
886	3216
887	3290
888	3559
889	3300
890	3685
891	3871
892	3890
893	3470
894	3346
895	3241
896	3352
897	3210
898	2866
899	2636
900	2609
901	2749
902	3083
903	3734
904	3810
905	3806
906	2917
907	2377
908	2796
909	3493
910	3392
911	2912
912	2768
913	3147
914	3162
915	3670
916	4402
917	4114
918	3314
919	4021
920	4496
921	4190
922	3775
923	3415
924	3368
925	3767
926	3776
927	3692
928	3898
929	3889
930	4138
931	4091
932	3535
933	3068
934	2623
935	2700
936	2647
937	2967
938	3146
939	3145
940	2944
941	3718
942	3541
943	2918
944	2733
945	3042
946	3333
947	3479
948	3322
949	3699
950	3671
951	3570
952	3034
953	2542
954	2786
955	2482
956	2582
957	3131
958	3738
959	3764
960	3497
961	2929
962	2970
963	3134
964	3545
965	3717
966	4022
967	4720
968	4711
969	3435
970	2958
971	3501
972	3533
973	3636
974	3806
975	3275
976	3024
977	2843
978	2887
979	3126
980	3688
981	3798
982	3546
983	3113
984	3459
985	3184
986	2640
987	2876
988	3585
989	3596
990	2985
991	3695
992	4303
993	3879
994	3303
995	3549
996	3742
997	3598
998	3482
999	3228
1000	3366
1001	3468
1002	3650
1003	3515
1004	3125
1005	3893
1006	4275
1007	3931
1008	3503
1009	3338
1010	3159
1011	3445
1012	4213
1013	4651
1014	3954
1015	3250
1016	3112
1017	3246
1018	3429
1019	3920
1020	3387
1021	3396
1022	2888
1023	2863
1024	3404