1	1658
2	1732
3	1841
4	1861
5	1703
6	1938
7	2386
8	2542
9	2948
10	2930
11	2835
12	2601
13	2632
14	2454
15	2529
16	2508
17	2526
18	2491
19	2464
20	2531
21	2540
22	2587
23	2649
24	2593
25	2601
26	2579
27	2533
28	2497
29	2185
30	1943
31	1920
32	1729
33	1820
34	1964
35	1859
36	1843
37	1830
38	1946
39	2066
40	2124
41	2436
42	2623
43	2775
44	2543
45	2410
46	2248
47	2332
48	2638
49	2812
50	2967
51	2931
52	2966
53	3120
54	3225
55	3225
56	2887
57	2916
58	2934
59	2945
60	2937
61	2830
62	2823
63	3105
64	3263
65	3166
66	3189
67	2896
68	2677
69	2271
70	2223
71	2192
72	2436
73	2640
74	2552
75	2323
76	2017
77	2177
78	2623
79	3104
80	3156
81	2905
82	2928
83	3190
84	3480
85	3862
86	4072
87	4044
88	3867
89	3615
90	3526
91	3292
92	3331
93	3497
94	3303
95	3271
96	3321
97	3776
98	4152
99	4028
100	3507
101	2876
102	2666
103	2359
104	2466
105	2367
106	2301
107	2620
108	2931
109	3419
110	3510
111	3056
112	2894
113	2875
114	2881
115	3128
116	3199
117	2896
118	2771
119	2452
120	1941
121	2086
122	2201
123	2324
124	2557
125	2784
126	2780
127	2930
128	3051
129	3054
130	3341
131	3576
132	4039
133	4109
134	4041
135	3750
136	3493
137	3440
138	3498
139	3426
140	3333
141	3094
142	2802
143	2806
144	2874
145	2900
146	3006
147	3057
148	2988
149	2945
150	2892
151	3089
152	3381
153	3623
154	3773
155	3456
156	2993
157	2809
158	2968
159	3133
160	3319
161	3307
162	3371
163	3172
164	3476
165	3590
166	3650
167	3525
168	3351
169	3190
170	3314
171	3372
172	3600
173	3451
174	3141
175	2848
176	3235
177	3648
178	4085
179	4491
180	4517
181	4338
182	4077
183	4066
184	3983
185	3961
186	3562
187	3228
188	3211
189	3689
190	4431
191	4806
192	4718
193	4440
194	4018
195	3865
196	3642
197	3613
198	3664
199	3784
200	3604
201	3551
202	3142
203	3219
204	3546
205	3718
206	3469
207	3624
208	3768
209	4078
210	4410
211	4308
212	4161
213	4125
214	4168
215	4478
216	4100
217	4062
218	4096
219	4357
220	4575
221	4444
222	4591
223	4749
224	4558
225	4147
226	3524
227	3364
228	3137
229	3125
230	3000
231	2775
232	2728
233	2980
234	3358
235	3710
236	4023
237	4277
238	4360
239	4241
240	4106
241	3805
242	3756
243	3661
244	4019
245	4286
246	4201
247	4299
248	4300
249	4334
250	4679
251	4958
252	5535
253	6387
254	6829
255	6768
256	6327
257	6389
258	6691
259	6556
260	5558
261	4540
262	3888
263	3972
264	3938
265	3918
266	3905
267	4190
268	4734
269	4788
270	4566
271	4698
272	5102
273	5283
274	5022
275	4311
276	4043
277	4196
278	4547
279	4752
280	4621
281	4470
282	4565
283	5314
284	5419
285	4878
286	3911
287	3453
288	3283
289	3490
290	4182
291	5234
292	5632
293	5733
294	5632
295	5643
296	5857
297	5782
298	5882
299	5785
300	5707
301	5243
302	5120
303	5335
304	5527
305	5629
306	5511
307	5024
308	4414
309	4599
310	4683
311	5014
312	5044
313	4919
314	4815
315	4529
316	4579
317	4640
318	4901
319	5095
320	5496
321	5925
322	6160
323	6026
324	5642
325	5114
326	5463
327	5442
328	5402
329	5280
330	5586
331	5635
332	5678
333	5479
334	5405
335	6219
336	7035
337	7344
338	7164
339	6657
340	6429
341	6901
342	7077
343	6869
344	6055
345	5532
346	5381
347	5905
348	6265
349	6557
350	6555
351	6515
352	6314
353	6618
354	6790
355	7628
356	8344
357	8670
358	8083
359	6916
360	6389
361	7121
362	8442
363	9281
364	8894
365	7730
366	6651
367	6451
368	6988
369	7814
370	8126
371	7597
372	7460
373	7185
374	6893
375	6536
376	6430
377	6517
378	7175
379	8096
380	8484
381	8241
382	7764
383	7427
384	7752
385	8316
386	8315
387	8169
388	8285
389	7964
390	7816
391	8239
392	8993
393	9319
394	8932
395	8531
396	8590
397	8628
398	8241
399	8307
400	8874
401	9406
402	9969
403	9481
404	8711
405	7932
406	8235
407	8389
408	8814
409	8573
410	8580
411	8501
412	8231
413	8592
414	9654
415	11068
416	11593
417	11231
418	11044
419	11014
420	10817
421	9964
422	9258
423	9128
424	9631
425	9966
426	10450
427	11055
428	11416
429	11144
430	10783
431	10330
432	10813
433	11129
434	10973
435	10543
436	10350
437	10750
438	11261
439	11584
440	12030
441	12541
442	12877
443	12392
444	11311
445	10168
446	10478
447	11828
448	13275
449	13451
450	12357
451	11390
452	10799
453	11088
454	11899
455	12440
456	11617
457	10895
458	10971
459	11652
460	12466
461	13726
462	14435
463	14008
464	13221
465	12267
466	12460
467	13463
468	14110
469	14779
470	14952
471	14632
472	14062
473	14169
474	13464
475	13090
476	14081
477	14973
478	14689
479	14425
480	14318
481	14371
482	15084
483	16733
484	17722
485	17315
486	17121
487	16722
488	17143
489	17320
490	17835
491	17769
492	16431
493	16181
494	16846
495	17110
496	16738
497	16821
498	17271
499	17486
500	17967
501	18396
502	19836
503	21854
504	21505
505	20244
506	19870
507	21189
508	22630
509	22960
510	23414
511	24407
512	24574
513	23086
514	21265
515	21228
516	22026
517	23516
518	24532
519	24531
520	25718
521	26036
522	25925
523	25320
524	23904
525	22907
526	24332
527	26840
528	29426
529	31281
530	31052
531	30345
532	28371
533	26584
534	24909
535	24711
536	24761
537	25266
538	26940
539	26799
540	25457
541	25984
542	29088
543	32439
544	32436
545	31576
546	30877
547	30967
548	28618
549	27339
550	28524
551	28443
552	27348
553	27536
554	28144
555	28167
556	29671
557	32003
558	31596
559	30101
560	30841
561	31643
562	31187
563	31025
564	33046
565	33699
566	33331
567	33824
568	33562
569	32101
570	32207
571	33479
572	33901
573	34881
574	35964
575	34471
576	32768
577	33082
578	34948
579	38071
580	40651
581	39704
582	36726
583	35276
584	33711
585	31846
586	31938
587	33959
588	34591
589	33906
590	32355
591	31617
592	32181
593	34192
594	34342
595	32122
596	30726
597	30464
598	31016
599	31914
600	31568
601	31725
602	30873
603	30103
604	30165
605	29955
606	28751
607	28501
608	28024
609	28494
610	30658
611	31098
612	31348
613	32850
614	32727
615	30180
616	27104
617	27013
618	28133
619	29742
620	29670
621	28826
622	28389
623	28058
624	28147
625	27299
626	25588
627	23386
628	23084
629	24256
630	25668
631	25989
632	24564
633	24130
634	24524
635	23895
636	22642
637	23113
638	23276
639	22189
640	20930
641	21251
642	21307
643	22270
644	24107
645	23249
646	20863
647	19028
648	18507
649	19146
650	19476
651	19958
652	20086
653	19384
654	19487
655	18846
656	18282
657	17323
658	17730
659	19922
660	22426
661	23359
662	22318
663	19895
664	19714
665	19355
666	18528
667	18957
668	19150
669	17875
670	17887
671	18287
672	16481
673	14971
674	15689
675	16770
676	17943
677	17852
678	17297
679	16161
680	15532
681	14453
682	13797
683	15651
684	17386
685	18222
686	16981
687	15875
688	15169
689	14380
690	13823
691	14266
692	14089
693	13899
694	14848
695	15316
696	15464
697	14497
698	13516
699	13353
700	13058
701	12432
702	10892
703	11179
704	11950
705	13137
706	12483
707	11794
708	13067
709	13296
710	13774
711	14333
712	13494
713	13782
714	14784
715	15424
716	15634
717	14146
718	12420
719	10695
720	9728
721	10537
722	11536
723	11046
724	10647
725	10852
726	11079
727	11466
728	11256
729	10812
730	10471
731	10866
732	11737
733	11580
734	11268
735	9972
736	8982
737	9796
738	11317
739	12507
740	12532
741	10972
742	10775
743	12105
744	12623
745	11510
746	9601
747	8454
748	8223
749	8780
750	10766
751	10993
752	10107
753	10277
754	10383
755	9887
756	9574
757	9932
758	9731
759	9456
760	9586
761	10124
762	10231
763	9769
764	8968
765	8592
766	7994
767	7775
768	7213
769	8258
770	8093
771	9174
772	10366
773	10258
774	8722
775	7153
776	7473
777	8453
778	8116
779	7510
780	7558
781	7297
782	7969
783	9095
784	9005
785	8385
786	8998
787	8949
788	7691
789	6472
790	6910
791	8565
792	9147
793	8532
794	7975
795	8662
796	10220
797	10002
798	7626
799	6612
800	6697
801	8453
802	9609
803	8743
804	7509
805	7616
806	7281
807	6423
808	6726
809	7116
810	6977
811	6652
812	6878
813	7689
814	8034
815	7887
816	7681
817	7302
818	6534
819	6954
820	7368
821	7387
822	8300
823	8635
824	8050
825	7156
826	6668
827	7036
828	7914
829	7869
830	6247
831	5831
832	6089
833	6051
834	5214
835	4825
836	5122
837	5557
838	6788
839	7522
840	6729
841	6129
842	5982
843	5862
844	5879
845	5845
846	6153
847	6432
848	5957
849	6393
850	7110
851	6195
852	4988
853	5331
854	6551
855	7170
856	6221
857	5922
858	6521
859	6813
860	6433
861	6074
862	6377
863	6831
864	6063
865	5513
866	4863
867	5166
868	5029
869	4931
870	4791
871	4871
872	5195
873	5936
874	4848
875	4425
876	4467
877	4888
878	5410
879	5274
880	5007
881	4560
882	3906
883	3434
884	4774
885	4888
886	4457
887	6018
888	5940
889	5384
890	5336
891	4560
892	2926
893	2215
894	2596
895	4467
896	5249
897	4430
898	5141
899	5533
900	4567
901	4205
902	4328
903	4721
904	5489
905	6840
906	6211
907	5751
908	6162
909	5079
910	3890
911	3919
912	4114
913	4562
914	4718
915	5249
916	5973
917	4997
918	4113
919	3936
920	3600
921	3708
922	4726
923	4672
924	4203
925	4680
926	4663
927	4180
928	4418
929	3682
930	3593
931	4850
932	4023
933	3028
934	2612
935	2565
936	2837
937	3307
938	3515
939	3904
940	3915
941	4665
942	5618
943	4950
944	4668
945	3860
946	3491
947	4019
948	4453
949	3988
950	4280
951	5683
952	6687
953	6362
954	5902
955	6370
956	6295
957	5086
958	5280
959	5991
960	6329
961	5773
962	5458
963	4653
964	3878
965	3679
966	3935
967	4283
968	4048
969	3930
970	2683
971	2635
972	2811
973	2813
974	2918
975	3862
976	4092
977	4355
978	4032
979	3720
980	4533
981	4935
982	4739
983	3959
984	3449
985	3106
986	3188
987	3395
988	3686
989	3778
990	3510
991	3333
992	3068
993	3563
994	3495
995	2777
996	2801
997	3477
998	4879
999	5878
1000	5511
1001	4708
1002	4566
1003	4445
1004	3592
1005	3627
1006	4097
1007	3266
1008	3869
1009	4298
1010	3235
1011	2680
1012	2866
1013	3875
1014	3863
1015	3355
1016	2764
1017	4305
1018	5538
1019	5701
1020	5669
1021	5089
1022	5467
1023	5199
1024	4638