1	3280
2	3693
3	4468
4	4850
5	4856
6	4247
7	3770
8	3030
9	2734
10	2673
11	2820
12	3474
13	4160
14	4695
15	5318
16	5505
17	5717
18	5873
19	5986
20	5859
21	5553
22	5161
23	4714
24	4186
25	4189
26	4454
27	4775
28	5245
29	5523
30	6120
31	6904
32	7539
33	7800
34	7335
35	6478
36	5493
37	4871
38	4303
39	4082
40	3762
41	4011
42	4626
43	4864
44	5088
45	5279
46	5910
47	7221
48	8146
49	8694
50	8017
51	6900
52	5483
53	4480
54	4076
55	3420
56	3299
57	3471
58	4252
59	5168
60	5298
61	5203
62	5183
63	5364
64	5819
65	6176
66	6586
67	6121
68	5465
69	5138
70	4630
71	4156
72	3461
73	3257
74	3592
75	4321
76	5080
77	5499
78	5520
79	5423
80	5936
81	6699
82	6927
83	6989
84	6591
85	5726
86	4757
87	4099
88	4131
89	4210
90	4536
91	4863
92	5623
93	6210
94	7032
95	7540
96	7920
97	7502
98	6056
99	4912
100	5037
101	5835
102	6745
103	7679
104	8150
105	8113
106	7694
107	7019
108	6117
109	5071
110	4324
111	4734
112	5593
113	6357
114	6985
115	7210
116	7075
117	6475
118	5766
119	4926
120	4566
121	4848
122	5497
123	6117
124	6243
125	5943
126	6001
127	6065
128	5820
129	5786
130	5351
131	4534
132	4345
133	4280
134	4493
135	4713
136	4759
137	5059
138	5746
139	6082
140	6843
141	8026
142	9214
143	9919
144	9738
145	8895
146	7908
147	7350
148	7299
149	7718
150	7923
151	8331
152	9938
153	10882
154	11638
155	10963
156	9944
157	9427
158	9063
159	8956
160	8785
161	8258
162	8429
163	9127
164	9384
165	9228
166	9172
167	9014
168	8440
169	7792
170	7437
171	7368
172	7148
173	6925
174	7680
175	9274
176	11225
177	12006
178	12042
179	11453
180	11190
181	11298
182	11592
183	11569
184	10790
185	10724
186	10453
187	10648
188	10600
189	10217
190	10459
191	11114
192	11601
193	12100
194	12672
195	13088
196	12374
197	12120
198	13381
199	14281
200	14126
201	13662
202	12650
203	12503
204	12316
205	12600
206	12769
207	14147
208	15891
209	18119
210	18975
211	19087
212	19267
213	19664
214	20193
215	20390
216	18858
217	16623
218	13758
219	12661
220	12148
221	12300
222	12059
223	11273
224	10234
225	9908
226	9980
227	10460
228	11791
229	12755
230	13429
231	12894
232	12891
233	13555
234	15117
235	15921
236	15407
237	13526
238	11971
239	11848
240	12325
241	13089
242	13466
243	13466
244	12901
245	11743
246	11148
247	10117
248	8503
249	7922
250	8736
251	10730
252	12604
253	14259
254	15574
255	16806
256	17209
257	16583
258	16301
259	18614
260	21958
261	24800
262	24601
263	21516
264	16907
265	12708
266	11315
267	11827
268	13135
269	13002
270	10958
271	9166
272	8644
273	9100
274	9548
275	9453
276	9852
277	10248
278	9919
279	9384
280	9688
281	10454
282	10479
283	9382
284	7926
285	7528
286	7790
287	8642
288	8928
289	8138
290	7894
291	7971
292	8571
293	9721
294	10745
295	10532
296	9307
297	8224
298	7863
299	7779
300	7295
301	7323
302	8040
303	9539
304	10402
305	9896
306	8695
307	7702
308	7660
309	7703
310	7736
311	7847
312	7913
313	9642
314	11645
315	11944
316	10297
317	9159
318	10075
319	10802
320	10173
321	8678
322	8347
323	9503
324	10949
325	11256
326	10988
327	10748
328	10052
329	10582
330	11655
331	12393
332	12650
333	12543
334	12011
335	12193
336	12471
337	12427
338	12718
339	13710
340	13710
341	12313
342	10798
343	9883
344	9719
345	10633
346	11096
347	10612
348	10029
349	10202
350	11051
351	11731
352	12286
353	12785
354	12356
355	11654
356	11908
357	13068
358	13634
359	12947
360	11478
361	10028
362	9660
363	10398
364	12496
365	14224
366	13423
367	11639
368	11353
369	12119
370	11898
371	11104
372	10542
373	10917
374	12054
375	13801
376	15827
377	15841
378	15140
379	15494
380	16386
381	17330
382	17394
383	16091
384	14571
385	12957
386	12192
387	14096
388	17207
389	18589
390	18226
391	17422
392	16460
393	16139
394	15716
395	14867
396	14794
397	14931
398	14717
399	14714
400	15495
401	16853
402	17715
403	17151
404	15964
405	15607
406	15735
407	15921
408	16078
409	15935
410	17454
411	17838
412	17957
413	18936
414	20620
415	20968
416	20421
417	19104
418	19902
419	20920
420	21510
421	19972
422	18702
423	17615
424	16846
425	16859
426	18608
427	19114
428	19846
429	21403
430	23795
431	25502
432	25480
433	23159
434	20465
435	19313
436	19603
437	19348
438	19036
439	19856
440	21626
441	22104
442	21322
443	21050
444	22778
445	22683
446	21973
447	20250
448	18346
449	16464
450	15704
451	16047
452	17472
453	19745
454	21584
455	23193
456	23535
457	22610
458	21503
459	23740
460	26523
461	26021
462	25603
463	25569
464	24649
465	23107
466	23946
467	24530
468	22297
469	19378
470	17374
471	19014
472	21862
473	23874
474	25145
475	25141
476	25243
477	25898
478	23490
479	18786
480	15865
481	17050
482	18639
483	19848
484	21615
485	23679
486	23808
487	21298
488	19212
489	18674
490	19828
491	21207
492	20165
493	18985
494	17738
495	17806
496	17805
497	16665
498	16520
499	18844
500	20687
501	19648
502	16535
503	14391
504	13930
505	14885
506	16119
507	15043
508	13546
509	13943
510	15024
511	15671
512	16308
513	16665
514	16735
515	16794
516	15501
517	13113
518	11148
519	10383
520	12085
521	13904
522	14104
523	12905
524	12986
525	13528
526	12888
527	12902
528	14311
529	15108
530	13011
531	9981
532	9710
533	11592
534	13250
535	14472
536	16140
537	15589
538	14445
539	13456
540	10716
541	9277
542	10104
543	10645
544	10461
545	11651
546	13210
547	12893
548	10719
549	9909
550	10239
551	9650
552	8582
553	9150
554	11654
555	12714
556	11702
557	9719
558	8013
559	8455
560	8863
561	10675
562	11968
563	11795
564	11830
565	10656
566	9872
567	10655
568	11390
569	10482
570	10026
571	10214
572	10078
573	8685
574	8817
575	10445
576	10196
577	8646
578	8017
579	8665
580	10217
581	10273
582	8957
583	8209
584	8218
585	8355
586	9179
587	10446
588	10993
589	9956
590	8192
591	6852
592	8103
593	9819
594	8982
595	6871
596	6582
597	6642
598	7151
599	9296
600	12941
601	14496
602	12379
603	10529
604	8979
605	8096
606	8073
607	7508
608	6179
609	5083
610	4595
611	5381
612	6947
613	7211
614	6469
615	7023
616	7480
617	7201
618	6922
619	6909
620	6135
621	5132
622	4972
623	6308
624	6391
625	6247
626	7100
627	7678
628	8298
629	7995
630	6814
631	5992
632	6087
633	6464
634	6918
635	7283
636	7030
637	6981
638	6037
639	5091
640	5439
641	6967
642	7094
643	6046
644	5271
645	5150
646	5318
647	6077
648	7073
649	6872
650	4917
651	3623
652	4584
653	5104
654	5204
655	4815
656	4454
657	4580
658	4470
659	5198
660	5051
661	3391
662	3701
663	6477
664	8276
665	7035
666	5485
667	4742
668	4839
669	5615
670	6523
671	5984
672	6072
673	7358
674	7415
675	5580
676	4200
677	3844
678	4016
679	4430
680	5087
681	5461
682	6659
683	7346
684	5934
685	4475
686	4465
687	6308
688	6953
689	6453
690	5759
691	6425
692	7760
693	7558
694	7080
695	6940
696	7039
697	5649
698	4589
699	5631
700	8173
701	8633
702	6661
703	7428
704	8915
705	9456
706	7373
707	5133
708	6870
709	10054
710	8976
711	5360
712	4414
713	5605
714	7895
715	8896
716	9478
717	10197
718	8981
719	7061
720	6122
721	7210
722	8209
723	6973
724	6683
725	7474
726	7474
727	8429
728	9681
729	10325
730	9927
731	10824
732	11115
733	8915
734	6571
735	8091
736	11402
737	11435
738	10492
739	9300
740	8422
741	9403
742	10003
743	9760
744	7621
745	7762
746	10897
747	12446
748	13301
749	13883
750	12184
751	9805
752	9829
753	10685
754	11162
755	8601
756	7263
757	7841
758	8767
759	10768
760	8319
761	6850
762	8161
763	10470
764	11567
765	12837
766	12293
767	11884
768	11624
769	11629
770	10918
771	9701
772	9371
773	9818
774	11702
775	12934
776	12553
777	13033
778	11125
779	8831
780	9564
781	10094
782	9339
783	9061
784	10525
785	9350
786	9063
787	10486
788	12167
789	12910
790	12726
791	11306
792	10797
793	10473
794	7299
795	5763
796	8228
797	11856
798	12846
799	12534
800	11179
801	9344
802	7605
803	9503
804	12779
805	13023
806	12705
807	11746
808	9806
809	9711
810	11694
811	11591
812	11365
813	13565
814	14255
815	11300
816	9677
817	10328
818	10734
819	12151
820	13545
821	11334
822	9029
823	8135
824	7478
825	8825
826	9118
827	7392
828	6639
829	8440
830	10519
831	10472
832	10914
833	11252
834	10498
835	8451
836	8667
837	8824
838	9862
839	8668
840	6627
841	7043
842	7628
843	7391
844	8276
845	10052
846	10544
847	10180
848	9621
849	9398
850	10257
851	10845
852	8449
853	6167
854	4974
855	7308
856	9788
857	8020
858	6298
859	6425
860	6694
861	7473
862	7622
863	6504
864	5305
865	5899
866	6208
867	4336
868	3016
869	4340
870	5998
871	6261
872	4401
873	3488
874	4350
875	7262
876	7806
877	6555
878	5387
879	4622
880	3952
881	4846
882	4731
883	4634
884	6205
885	6785
886	5213
887	4296
888	4407
889	5690
890	7532
891	6836
892	4363
893	3120
894	3686
895	4310
896	5307
897	5908
898	6072
899	6928
900	7665
901	7041
902	4059
903	2491
904	2862
905	3370
906	4343
907	4222
908	2628
909	2664
910	3998
911	4965
912	4352
913	3858
914	3702
915	4590
916	4880
917	5410
918	5241
919	4914
920	5203
921	4765
922	4414
923	6019
924	6126
925	4554
926	4026
927	4277
928	6167
929	8620
930	6623
931	4161
932	3504
933	5825
934	7193
935	5266
936	3827
937	3757
938	4757
939	4030
940	3033
941	3212
942	5685
943	6767
944	5347
945	3681
946	3324
947	3722
948	4036
949	4777
950	3552
951	2735
952	3396
953	4596
954	3833
955	3048
956	3409
957	3305
958	2478
959	3841
960	5166
961	4610
962	5473
963	5142
964	3375
965	3120
966	3689
967	2650
968	2113
969	2487
970	1960
971	1313
972	1817
973	2800
974	3975
975	3954
976	2924
977	3735
978	4318
979	3669
980	2840
981	4710
982	5736
983	6811
984	7859
985	6256
986	7311
987	7155
988	4620
989	3554
990	3749
991	4613
992	5013
993	7718
994	7090
995	5405
996	4564
997	3855
998	4853
999	4902
1000	3732
1001	3001
1002	2164
1003	1975
1004	3254
1005	4144
1006	5470
1007	4840
1008	4110
1009	3627
1010	4002
1011	2731
1012	1380
1013	1373
1014	2788
1015	5107
1016	5467
1017	4388
1018	3718
1019	2762
1020	3320
1021	3600
1022	3700
1023	4496
1024	4506