1	3496
2	3452
3	3453
4	3424
5	3509
6	3731
7	3773
8	3654
9	3569
10	3454
11	3575
12	3682
13	4003
14	3967
15	3851
16	3668
17	3330
18	3357
19	3257
20	3417
21	3790
22	3924
23	4048
24	4052
25	3854
26	3541
27	3532
28	3641
29	3611
30	3701
31	3818
32	3875
33	3515
34	3339
35	3252
36	3084
37	3404
38	3415
39	3832
40	3973
41	3992
42	3914
43	3852
44	3802
45	4079
46	4079
47	4043
48	4243
49	4557
50	4489
51	4297
52	3750
53	3864
54	4006
55	3947
56	3786
57	4272
58	4325
59	4490
60	4186
61	4075
62	3981
63	3959
64	4004
65	4146
66	4296
67	4553
68	4640
69	4827
70	4943
71	4848
72	4699
73	4685
74	4655
75	4826
76	5018
77	5198
78	5200
79	5084
80	5171
81	5190
82	5595
83	5688
84	5914
85	6149
86	6192
87	6343
88	6382
89	6748
90	7159
91	7499
92	8024
93	8347
94	8734
95	8864
96	9041
97	9294
98	9583
99	10121
100	10375
101	10372
102	10432
103	10775
104	11788
105	13056
106	14321
107	16132
108	17688
109	18804
110	20908
111	22830
112	25224
113	27626
114	29678
115	32244
116	34976
117	37713
118	39062
119	39651
120	39761
121	39843
122	39468
123	38027
124	36058
125	34165
126	31735
127	29660
128	27152
129	25116
130	23078
131	20818
132	19232
133	17584
134	16447
135	15516
136	14441
137	13496
138	12614
139	11543
140	10956
141	10474
142	10611
143	10313
144	9918
145	9169
146	8291
147	7386
148	7056
149	6987
150	7095
151	7193
152	7002
153	6834
154	6483
155	6519
156	6443
157	6311
158	5928
159	5480
160	5415
161	5462
162	5738
163	5810
164	5927
165	5661
166	5430
167	4974
168	4585
169	4581
170	4598
171	4954
172	5105
173	5431
174	5696
175	5662
176	5529
177	5089
178	4886
179	4856
180	5185
181	5095
182	4909
183	4544
184	4440
185	4417
186	4442
187	4431
188	4390
189	4375
190	4302
191	4342
192	4576
193	4801
194	4432
195	4074
196	3729
197	3785
198	3810
199	3755
200	3615
201	3758
202	3763
203	3953
204	3710
205	3609
206	3636
207	3630
208	3735
209	3715
210	3950
211	4212
212	4388
213	4243
214	4081
215	3933
216	4204
217	4568
218	4779
219	4412
220	4120
221	3973
222	4299
223	4199
224	4351
225	4270
226	4145
227	4239
228	4022
229	3943
230	3864
231	3783
232	3814
233	3637
234	3251
235	3075
236	3000
237	3057
238	3181
239	3230
240	3486
241	3896
242	4268
243	4507
244	4244
245	4158
246	4057
247	4175
248	4417
249	4662
250	4606
251	4171
252	4031
253	3896
254	3814
255	3551
256	3435
257	3664
258	3849
259	4186
260	4403
261	4494
262	4581
263	4389
264	4194
265	3915
266	3896
267	3611
268	3573
269	3991
270	4475
271	4597
272	4672
273	4718
274	4781
275	5036
276	4849
277	4457
278	4193
279	4236
280	4523
281	4783
282	4676
283	4376
284	4075
285	3999
286	4217
287	4437
288	4599
289	4645
290	4836
291	5294
292	5695
293	5797
294	5600
295	5210
296	5079
297	5026
298	5170
299	5671
300	6232
301	6329
302	6175
303	6195
304	6105
305	6093
306	6108
307	6193
308	6269
309	6476
310	7290
311	7707
312	8053
313	8612
314	8956
315	9147
316	9770
317	10478
318	11333
319	12163
320	12798
321	13684
322	14395
323	14689
324	14723
325	15301
326	15498
327	15399
328	14989
329	14773
330	14443
331	14058
332	13084
333	12183
334	11637
335	11360
336	10980
337	10573
338	10073
339	9711
340	9297
341	8822
342	8521
343	8447
344	8850
345	8785
346	8674
347	9169
348	9615
349	9828
350	10248
351	10496
352	10616
353	10240
354	10363
355	10110
356	9988
357	9638
358	9272
359	8794
360	8530
361	8466
362	8476
363	8240
364	8012
365	7674
366	7234
367	7003
368	6776
369	6496
370	6405
371	6444
372	6606
373	6924
374	6832
375	6905
376	6791
377	6561
378	6356
379	6404
380	6826
381	7193
382	7216
383	6823
384	6541
385	6784
386	6970
387	7028
388	7153
389	6875
390	6406
391	6366
392	6453
393	7181
394	7442
395	7171
396	7158
397	7282
398	7751
399	7814
400	7755
401	8139
402	8587
403	8536
404	8451
405	8802
406	10196
407	10794
408	11066
409	11146
410	10925
411	10896
412	11244
413	11928
414	12741
415	13892
416	14597
417	15283
418	15918
419	16710
420	17647
421	18472
422	19071
423	19142
424	17618
425	16077
426	15914
427	16342
428	16492
429	16140
430	15977
431	15609
432	14928
433	14493
434	14068
435	13151
436	12055
437	11067
438	10414
439	9782
440	10333
441	10379
442	10942
443	11537
444	12098
445	12184
446	12420
447	12396
448	12984
449	13838
450	14567
451	14257
452	13580
453	13418
454	14196
455	15043
456	15412
457	15659
458	16007
459	17168
460	17992
461	18804
462	19714
463	21000
464	22592
465	24050
466	25773
467	26868
468	27129
469	28751
470	30253
471	32732
472	33442
473	34053
474	33955
475	35269
476	36886
477	39676
478	41627
479	42890
480	43480
481	44844
482	46627
483	47510
484	47099
485	46641
486	47214
487	47269
488	45434
489	43151
490	42560
491	41547
492	39635
493	38721
494	38598
495	38511
496	37573
497	37009
498	37565
499	37525
500	38350
501	39268
502	40171
503	41114
504	42683
505	45547
506	49381
507	52732
508	55831
509	57928
510	60835
511	63388
512	66486
513	70326
514	73988
515	77423
516	78297
517	78236
518	79835
519	82648
520	85793
521	87208
522	88094
523	87640
524	88654
525	90856
526	94416
527	97455
528	98861
529	103174
530	109252
531	115843
532	122381
533	128969
534	134595
535	141062
536	152439
537	163248
538	171926
539	175618
540	177551
541	180448
542	178601
543	176567
544	172133
545	163556
546	152802
547	143375
548	136088
549	127585
550	119875
551	113290
552	106713
553	101259
554	96392
555	91985
556	90262
557	89963
558	88015
559	86706
560	87120
561	86513
562	90219
563	93403
564	96776
565	100311
566	104742
567	106597
568	111586
569	117032
570	124697
571	132767
572	140883
573	147705
574	152246
575	162558
576	171596
577	180922
578	188971
579	194081
580	197388
581	195834
582	192359
583	186422
584	179010
585	168871
586	157202
587	150025
588	140360
589	130128
590	119085
591	110290
592	104005
593	97368
594	90267
595	80165
596	71514
597	64765
598	61342
599	58497
600	54669
601	51656
602	49072
603	47443
604	45151
605	41747
606	39929
607	38958
608	36390
609	34676
610	33808
611	32526
612	30631
613	29197
614	27224
615	26485
616	25353
617	24832
618	24246
619	23638
620	24654
621	26534
622	26708
623	25219
624	22996
625	22534
626	22498
627	21644
628	21149
629	21843
630	23383
631	23863
632	22657
633	21000
634	20558
635	20739
636	20801
637	21424
638	21806
639	22636
640	24003
641	25539
642	25961
643	26026
644	26780
645	29028
646	31062
647	31810
648	33209
649	34551
650	36881
651	38812
652	39210
653	38439
654	39226
655	40087
656	40743
657	41256
658	38619
659	36851
660	36124
661	34377
662	32165
663	28865
664	25917
665	23937
666	23512
667	22936
668	21247
669	19883
670	18898
671	18734
672	18910
673	18309
674	17504
675	16197
676	15205
677	13739
678	13499
679	13720
680	13404
681	13816
682	13862
683	13744
684	13938
685	14543
686	13943
687	12925
688	13199
689	13447
690	13606
691	13563
692	13247
693	12089
694	11143
695	10529
696	9694
697	8948
698	9365
699	9484
700	9430
701	9528
702	9889
703	10053
704	9488
705	9439
706	10119
707	10115
708	9600
709	9316
710	9356
711	9384
712	9746
713	10149
714	10523
715	10442
716	10523
717	11168
718	11318
719	10960
720	10538
721	10506
722	11580
723	11978
724	12453
725	12641
726	13289
727	14192
728	14793
729	14783
730	15502
731	15478
732	14369
733	13227
734	12364
735	11381
736	11536
737	11360
738	10906
739	11015
740	11033
741	9413
742	8687
743	8714
744	8454
745	7801
746	7382
747	6972
748	6825
749	6930
750	6940
751	6501
752	6324
753	6044
754	5386
755	5409
756	5791
757	6769
758	6712
759	5867
760	5721
761	5424
762	5262
763	5154
764	4958
765	4530
766	4352
767	4196
768	4258
769	4339
770	4768
771	4979
772	4752
773	4777
774	4668
775	4488
776	4366
777	4800
778	4457
779	3957
780	4057
781	4901
782	5208
783	4761
784	4658
785	4488
786	4678
787	4987
788	4797
789	4126
790	3784
791	4163
792	4119
793	4259
794	4490
795	4516
796	4482
797	4101
798	4225
799	3982
800	4005
801	3969
802	3173
803	2816
804	3386
805	3699
806	3924
807	3670
808	3190
809	3354
810	3496
811	3902
812	4060
813	4021
814	3968
815	3980
816	4204
817	4268
818	3807
819	3853
820	3893
821	3372
822	3018
823	2910
824	3104
825	3423
826	3799
827	3869
828	4026
829	4848
830	3951
831	3241
832	3629
833	4263
834	3810
835	3236
836	3342
837	3628
838	4305
839	4502
840	4245
841	4026
842	4051
843	4055
844	4300
845	4114
846	3555
847	3561
848	4116
849	3982
850	3669
851	3530
852	3377
853	3826
854	4360
855	4301
856	4256
857	4244
858	3678
859	3206
860	3464
861	3492
862	3834
863	4187
864	4048
865	3899
866	3302
867	3048
868	3352
869	3069
870	2753
871	2917
872	3205
873	3578
874	3255
875	2761
876	2692
877	2821
878	3013
879	3330
880	3760
881	3698
882	3558
883	3525
884	3974
885	3787
886	3379
887	3941
888	4439
889	3515
890	3103
891	3039
892	3171
893	3177
894	3657
895	3687
896	3666
897	3058
898	3248
899	3329
900	3233
901	3495
902	4354
903	3948
904	3310
905	3111
906	3795
907	4583
908	3698
909	3173
910	3024
911	2959
912	3150
913	3313
914	3618
915	4216
916	4673
917	4077
918	4007
919	3674
920	3801
921	3886
922	4010
923	3617
924	3248
925	3590
926	4150
927	3820
928	3483
929	3682
930	3745
931	4132
932	4488
933	3715
934	3649
935	4161
936	4265
937	3755
938	3461
939	3618
940	3610
941	3391
942	3169
943	2902
944	3329
945	3106
946	3170
947	3304
948	3270
949	2819
950	3157
951	3525
952	3178
953	3177
954	3724
955	3584
956	3104
957	2891
958	2846
959	3342
960	3880
961	3060
962	2923
963	3695
964	4561
965	3911
966	3719
967	4089
968	3561
969	3621
970	3513
971	3169
972	2653
973	3370
974	3659
975	3926
976	3555
977	2931
978	3336
979	3905
980	3475
981	3159
982	3048
983	2764
984	2766
985	2791
986	2474
987	3488
988	3598
989	3321
990	3333
991	3624
992	3716
993	3232
994	3028
995	3542
996	3406
997	3346
998	2877
999	2589
1000	3317
1001	3220
1002	2774
1003	2793
1004	3082
1005	3105
1006	3401
1007	3232
1008	2809
1009	2764
1010	2886
1011	2702
1012	3277
1013	3099
1014	2963
1015	3022
1016	3029
1017	3243
1018	3389
1019	3906
1020	4321
1021	4080
1022	3922
1023	3850
1024	3565