1	2440
2	2539
3	2596
4	2712
5	2885
6	2720
7	2572
8	2776
9	3053
10	2732
11	2635
12	2605
13	2568
14	2261
15	2307
16	2058
17	1848
18	1565
19	1961
20	1858
21	2427
22	2212
23	2320
24	2501
25	2561
26	2164
27	1848
28	2207
29	2423
30	3309
31	2962
32	2856
33	2741
34	2124
35	2048
36	2318
37	2559
38	2487
39	2463
40	2346
41	2555
42	3038
43	3261
44	3529
45	3710
46	4005
47	3794
48	3221
49	2413
50	2679
51	2831
52	3220
53	3485
54	3586
55	3388
56	3091
57	2907
58	2866
59	2809
60	3028
61	3046
62	3041
63	2962
64	2818
65	2946
66	3134
67	3406
68	3066
69	2796
70	2383
71	2306
72	3013
73	3434
74	3428
75	3081
76	3345
77	3775
78	3927
79	3549
80	3494
81	3752
82	3549
83	3459
84	3524
85	3703
86	3269
87	3529
88	3740
89	3591
90	3716
91	3839
92	3863
93	3799
94	3470
95	3197
96	2743
97	2552
98	2857
99	3162
100	3408
101	3248
102	3047
103	3068
104	3027
105	2862
106	3261
107	3245
108	3075
109	2561
110	2397
111	2787
112	3298
113	3382
114	3327
115	3320
116	3588
117	3583
118	3982
119	3927
120	3524
121	3508
122	3669
123	3135
124	2819
125	2495
126	2556
127	2591
128	3036
129	3567
130	3836
131	3978
132	3582
133	3613
134	3087
135	2860
136	3241
137	2845
138	2851
139	3099
140	3272
141	3475
142	3480
143	3826
144	3884
145	3884
146	3655
147	3189
148	3049
149	3031
150	3418
151	3513
152	3979
153	4315
154	4377
155	3949
156	3600
157	3508
158	4046
159	4787
160	4769
161	4976
162	4920
163	4327
164	4017
165	4511
166	4432
167	4502
168	4656
169	4202
170	4178
171	3938
172	3486
173	3169
174	3244
175	3674
176	4228
177	4554
178	4701
179	4413
180	3951
181	3867
182	3541
183	3825
184	4252
185	4133
186	4260
187	4011
188	4014
189	4282
190	4331
191	4589
192	4545
193	4986
194	4816
195	4795
196	4676
197	5003
198	5144
199	5044
200	4798
201	4707
202	4929
203	5494
204	5692
205	5538
206	4850
207	4536
208	5035
209	4865
210	4634
211	4608
212	4972
213	4953
214	5114
215	5366
216	5169
217	5512
218	6024
219	5104
220	4250
221	3775
222	3863
223	4350
224	4486
225	4575
226	4713
227	5161
228	6001
229	6126
230	6131
231	6121
232	6111
233	5250
234	5350
235	5750
236	5647
237	6107
238	6311
239	5977
240	6014
241	6009
242	6326
243	5834
244	5803
245	5888
246	5871
247	5696
248	5571
249	5390
250	5097
251	5107
252	5506
253	5944
254	6344
255	6643
256	6655
257	6395
258	6343
259	5889
260	6212
261	6290
262	6266
263	5946
264	5779
265	5583
266	5701
267	6344
268	6418
269	6727
270	7056
271	6587
272	6530
273	6780
274	6988
275	7274
276	7410
277	7229
278	7088
279	7303
280	7610
281	7359
282	7957
283	7867
284	7137
285	6775
286	7099
287	6840
288	7283
289	7663
290	8192
291	8794
292	8867
293	8604
294	8170
295	8003
296	8022
297	7996
298	8815
299	8729
300	7735
301	6649
302	6558
303	7644
304	8915
305	8561
306	7556
307	7825
308	7796
309	8460
310	9002
311	8667
312	8277
313	7675
314	7408
315	7229
316	7017
317	6788
318	7356
319	7907
320	7860
321	7803
322	7444
323	7644
324	7522
325	7124
326	6795
327	6933
328	7113
329	7305
330	7302
331	7102
332	7489
333	7665
334	7689
335	8365
336	8545
337	9212
338	10876
339	10439
340	10260
341	9622
342	8462
343	8264
344	7514
345	7779
346	8306
347	9236
348	9728
349	9836
350	9548
351	9710
352	10094
353	10098
354	10368
355	10463
356	11117
357	11722
358	11555
359	12597
360	12830
361	11674
362	10429
363	9296
364	9058
365	8961
366	9436
367	10073
368	10203
369	9655
370	9779
371	11240
372	12752
373	12711
374	12290
375	12169
376	11306
377	11772
378	12029
379	11929
380	12490
381	11649
382	11398
383	11607
384	12882
385	13402
386	13567
387	13007
388	12121
389	12002
390	12331
391	12243
392	12688
393	11618
394	11547
395	12379
396	12696
397	12399
398	12690
399	13132
400	13190
401	12924
402	13516
403	14025
404	13786
405	13857
406	14989
407	15059
408	15169
409	15250
410	16102
411	17134
412	17890
413	18118
414	18008
415	17525
416	17406
417	17379
418	18473
419	17663
420	17668
421	17774
422	18397
423	18454
424	18262
425	19105
426	20405
427	20867
428	20696
429	19622
430	20376
431	19519
432	19016
433	17128
434	15827
435	15022
436	15013
437	16173
438	17601
439	18452
440	19315
441	20300
442	21686
443	22511
444	22363
445	21929
446	21146
447	20347
448	20643
449	20445
450	19884
451	20327
452	20675
453	21511
454	22304
455	21816
456	21447
457	22050
458	22881
459	23217
460	21949
461	21089
462	20891
463	20445
464	21878
465	22132
466	23446
467	25044
468	25205
469	25605
470	26095
471	24623
472	23673
473	22327
474	23386
475	25949
476	26667
477	26813
478	27761
479	29178
480	29711
481	30790
482	33817
483	34531
484	33077
485	31080
486	30787
487	30370
488	31299
489	32819
490	32669
491	31905
492	31555
493	32345
494	32446
495	34283
496	34546
497	34234
498	34566
499	35844
500	37062
501	38434
502	38908
503	38780
504	36928
505	35981
506	37552
507	40175
508	39745
509	39976
510	40998
511	39984
512	37174
513	36433
514	36534
515	38652
516	40887
517	43288
518	43956
519	42758
520	42904
521	44352
522	45966
523	48156
524	50982
525	51027
526	51695
527	51792
528	49897
529	46719
530	46758
531	48422
532	50198
533	49412
534	48737
535	50472
536	51920
537	52464
538	53294
539	52642
540	51936
541	54432
542	57736
543	59351
544	59572
545	59866
546	57575
547	55328
548	52871
549	52707
550	57076
551	60153
552	58555
553	58195
554	56928
555	54376
556	56517
557	57899
558	56125
559	52922
560	54159
561	58035
562	60272
563	61988
564	61301
565	62403
566	63264
567	59523
568	60726
569	62451
570	64461
571	66971
572	64770
573	64850
574	63930
575	61018
576	63540
577	64718
578	62240
579	62774
580	62477
581	62220
582	64177
583	65678
584	66311
585	66376
586	66107
587	65218
588	64206
589	63491
590	64941
591	64859
592	66797
593	67142
594	66971
595	67143
596	64827
597	65760
598	68705
599	66801
600	62388
601	61793
602	60559
603	55068
604	54728
605	54090
606	54507
607	52542
608	50234
609	47901
610	48871
611	49715
612	49776
613	51175
614	52953
615	50067
616	44199
617	43310
618	46665
619	50490
620	48370
621	45215
622	45054
623	44680
624	46406
625	45317
626	42609
627	41169
628	42078
629	45021
630	46879
631	46579
632	44945
633	40309
634	39891
635	40939
636	37716
637	35409
638	38179
639	38133
640	37158
641	39082
642	38049
643	39294
644	37960
645	38198
646	38549
647	36930
648	35813
649	36255
650	35438
651	33346
652	34611
653	36830
654	37342
655	35874
656	32608
657	33194
658	34693
659	34811
660	31634
661	30385
662	27870
663	26269
664	26973
665	30606
666	33317
667	32994
668	31281
669	29628
670	28082
671	26222
672	25690
673	25970
674	27746
675	27469
676	27283
677	24944
678	23300
679	24754
680	26467
681	24159
682	22861
683	23058
684	23233
685	23446
686	23385
687	25162
688	25846
689	26649
690	25306
691	22787
692	20504
693	20543
694	21752
695	23748
696	24800
697	23278
698	20954
699	18721
700	19881
701	22932
702	23550
703	22684
704	20488
705	19403
706	19182
707	19834
708	19419
709	20143
710	18419
711	18628
712	18516
713	17902
714	16715
715	15661
716	15041
717	15454
718	15232
719	16686
720	18295
721	19010
722	18398
723	17280
724	17450
725	17886
726	18119
727	17916
728	17128
729	17121
730	16076
731	16076
732	16161
733	14269
734	13885
735	14947
736	13506
737	13235
738	13730
739	13685
740	14914
741	14778
742	14188
743	14733
744	14931
745	13625
746	12952
747	12053
748	10566
749	11196
750	11733
751	12509
752	13067
753	14875
754	14153
755	12486
756	10835
757	10666
758	10668
759	10979
760	11164
761	12920
762	14726
763	15903
764	14741
765	14167
766	14762
767	13473
768	13167
769	12330
770	11880
771	11875
772	11735
773	12643
774	12169
775	10710
776	10171
777	9632
778	9298
779	9409
780	9832
781	9232
782	9101
783	8944
784	9190
785	9687
786	10102
787	9471
788	9031
789	9471
790	10179
791	9288
792	9575
793	8672
794	9126
795	8433
796	9216
797	9463
798	9502
799	8575
800	9247
801	9597
802	9639
803	9362
804	9378
805	7780
806	7645
807	8311
808	8064
809	8016
810	7944
811	8233
812	8451
813	9098
814	10324
815	10092
816	9823
817	10018
818	10477
819	10086
820	8981
821	9146
822	8892
823	8903
824	8581
825	9867
826	9903
827	9515
828	8684
829	7561
830	7195
831	7448
832	7403
833	7491
834	6841
835	6732
836	6763
837	7430
838	8680
839	8001
840	7484
841	7217
842	6955
843	6424
844	6057
845	6139
846	7923
847	8980
848	7676
849	5817
850	5854
851	6760
852	5916
853	6341
854	8160
855	8493
856	7026
857	6154
858	6158
859	7136
860	7504
861	7284
862	7211
863	6420
864	5788
865	6108
866	6079
867	6048
868	5416
869	5555
870	6388
871	6056
872	4888
873	4899
874	4359
875	4652
876	5591
877	5762
878	4737
879	4665
880	6077
881	6188
882	6047
883	6646
884	6405
885	5857
886	5372
887	4330
888	4894
889	5300
890	6144
891	7148
892	7253
893	6909
894	7819
895	6685
896	5431
897	5456
898	4779
899	4582
900	5596
901	5689
902	6462
903	6132
904	5653
905	5884
906	6248
907	6414
908	6189
909	6174
910	5196
911	4224
912	4348
913	4835
914	5164
915	5331
916	6049
917	6897
918	6472
919	5267
920	4525
921	4535
922	5059
923	3986
924	3834
925	4007
926	4394
927	5388
928	5939
929	6385
930	6688
931	5633
932	3740
933	4480
934	4828
935	4529
936	3656
937	2633
938	2716
939	2844
940	3179
941	3820
942	4498
943	4458
944	3996
945	4027
946	4317
947	5436
948	6075
949	5289
950	4148
951	4123
952	4113
953	4646
954	4988
955	4751
956	4008
957	3787
958	4261
959	4356
960	4112
961	4794
962	4761
963	5759
964	6677
965	6444
966	3972
967	3493
968	4580
969	4299
970	4009
971	3716
972	3880
973	3368
974	3429
975	4075
976	5331
977	4595
978	4007
979	3953
980	4789
981	5033
982	5017
983	4418
984	3679
985	4180
986	4317
987	3986
988	3134
989	3976
990	3725
991	3293
992	3449
993	3965
994	3020
995	2921
996	3452
997	4250
998	4123
999	3790
1000	3901
1001	4106
1002	4605
1003	5342
1004	5013
1005	3361
1006	4699
1007	5060
1008	3754
1009	3941
1010	3006
1011	3101
1012	3686
1013	3806
1014	3267
1015	2706
1016	2933
1017	4114
1018	5085
1019	4582
1020	4100
1021	2867
1022	3746
1023	2840
1024	2676