1	6808
2	6715
3	6754
4	6320
5	5765
6	5193
7	4939
8	5290
9	6435
10	7476
11	7598
12	7147
13	6216
14	5303
15	4565
16	4285
17	4293
18	4071
19	3999
20	4628
21	5234
22	5396
23	4854
24	3953
25	4098
26	4568
27	5169
28	5705
29	5446
30	5024
31	4483
32	3648
33	3269
34	3145
35	3608
36	4126
37	4563
38	4754
39	4401
40	3896
41	3519
42	3405
43	3476
44	3907
45	4811
46	5696
47	5881
48	4976
49	4096
50	3866
51	3960
52	4664
53	4808
54	4784
55	4140
56	3705
57	3519
58	3686
59	4586
60	5980
61	6592
62	6162
63	5494
64	5033
65	4980
66	5156
67	5615
68	5458
69	5460
70	5546
71	5640
72	5905
73	6505
74	7348
75	7883
76	7580
77	6937
78	6360
79	6445
80	6840
81	7455
82	7906
83	7925
84	7682
85	7293
86	7186
87	6895
88	6013
89	4803
90	4658
91	5522
92	6766
93	7185
94	7247
95	6468
96	5906
97	5296
98	5152
99	5621
100	6040
101	6268
102	6953
103	7428
104	7347
105	6407
106	5383
107	4428
108	4047
109	4155
110	4564
111	5350
112	6068
113	6868
114	7251
115	7497
116	7436
117	6802
118	5816
119	5005
120	4663
121	5401
122	6430
123	7107
124	7004
125	6199
126	5423
127	5031
128	5000
129	5009
130	5355
131	5521
132	5529
133	5543
134	5363
135	4720
136	3984
137	4298
138	5247
139	6069
140	6724
141	7355
142	7922
143	8329
144	7734
145	7063
146	6421
147	5875
148	5391
149	5423
150	6012
151	6520
152	7057
153	6720
154	6382
155	6293
156	5996
157	6417
158	7004
159	7237
160	6757
161	5857
162	5477
163	5883
164	6785
165	7794
166	9078
167	10798
168	12283
169	12319
170	11047
171	9783
172	8803
173	8587
174	8558
175	7800
176	7542
177	7652
178	8884
179	10327
180	11296
181	11548
182	11863
183	12122
184	11931
185	10981
186	10030
187	9822
188	9725
189	9712
190	9690
191	9743
192	9809
193	10355
194	10633
195	11395
196	11298
197	11392
198	10858
199	10616
200	10660
201	10657
202	10728
203	11024
204	10936
205	10768
206	10936
207	12048
208	12543
209	13654
210	14966
211	15631
212	14784
213	13205
214	11075
215	10012
216	10854
217	12593
218	14476
219	14803
220	13119
221	11273
222	9992
223	10507
224	11101
225	12255
226	12555
227	12580
228	12720
229	12847
230	13478
231	14201
232	14834
233	14327
234	12963
235	12172
236	13220
237	14891
238	15533
239	15144
240	13912
241	12828
242	11511
243	10528
244	10203
245	10388
246	10992
247	11296
248	11978
249	11474
250	10659
251	10216
252	10524
253	11319
254	11384
255	10879
256	10894
257	12121
258	13655
259	14610
260	14493
261	14616
262	14339
263	13922
264	13612
265	12442
266	12071
267	12493
268	13764
269	15414
270	16955
271	18063
272	16535
273	13594
274	11458
275	10997
276	12168
277	13113
278	13415
279	13170
280	12161
281	10782
282	10056
283	9761
284	10189
285	11008
286	11348
287	10675
288	9894
289	9713
290	9696
291	10401
292	11212
293	12488
294	13526
295	12461
296	10906
297	9312
298	8283
299	8321
300	8669
301	9914
302	10871
303	11459
304	11987
305	12686
306	12761
307	11073
308	9937
309	9247
310	9175
311	8675
312	8247
313	8504
314	9023
315	9774
316	10184
317	10923
318	11567
319	11407
320	9949
321	9610
322	9670
323	9657
324	8997
325	8195
326	8363
327	9210
328	10415
329	11390
330	11317
331	9819
332	9100
333	8485
334	8934
335	9804
336	10104
337	9998
338	10329
339	11077
340	11542
341	11900
342	12108
343	12042
344	10894
345	9713
346	7662
347	6911
348	6748
349	6377
350	6943
351	8985
352	12115
353	14082
354	14224
355	13076
356	11216
357	9842
358	10161
359	11393
360	12797
361	12555
362	11092
363	10410
364	11021
365	11776
366	12532
367	12473
368	12359
369	12712
370	13134
371	12096
372	10173
373	9644
374	9983
375	11322
376	13264
377	13592
378	13069
379	12731
380	12860
381	13259
382	15024
383	18566
384	21253
385	19454
386	15634
387	13709
388	12924
389	12817
390	12349
391	12116
392	11345
393	10296
394	10616
395	12639
396	12862
397	11515
398	10276
399	10379
400	11524
401	12538
402	13633
403	15294
404	17029
405	18122
406	17894
407	17088
408	16451
409	16192
410	17721
411	19165
412	19461
413	18744
414	17602
415	15970
416	16123
417	17484
418	18152
419	16889
420	16019
421	16295
422	16332
423	16516
424	15634
425	15379
426	16066
427	15943
428	15980
429	15659
430	15890
431	16574
432	18312
433	20013
434	21663
435	21476
436	18882
437	17691
438	17202
439	15829
440	14773
441	15471
442	17912
443	19076
444	18927
445	17421
446	17287
447	17053
448	16168
449	15231
450	16176
451	17672
452	18089
453	16776
454	15075
455	16292
456	19237
457	19295
458	16863
459	14911
460	14571
461	16769
462	20019
463	22914
464	23980
465	23722
466	22460
467	21073
468	19090
469	18393
470	16458
471	13337
472	11363
473	11628
474	13796
475	16986
476	18722
477	17849
478	17236
479	20230
480	22854
481	22003
482	19747
483	18687
484	20474
485	22756
486	25310
487	25691
488	24909
489	23572
490	21293
491	18407
492	16081
493	15268
494	14840
495	15220
496	15952
497	17133
498	18090
499	17338
500	16346
501	16383
502	18314
503	21006
504	21666
505	18862
506	16901
507	16339
508	16077
509	16365
510	19385
511	21738
512	21294
513	19507
514	18749
515	19697
516	19556
517	17462
518	15298
519	15439
520	16940
521	16742
522	15175
523	14248
524	13860
525	13208
526	12591
527	15014
528	19153
529	19217
530	16409
531	14369
532	14029
533	14683
534	13867
535	12762
536	12505
537	11695
538	10127
539	10455
540	11669
541	12164
542	11800
543	11796
544	11751
545	11028
546	10786
547	11217
548	10862
549	11505
550	12737
551	13224
552	14539
553	15840
554	15272
555	12725
556	10018
557	10229
558	13426
559	14245
560	12886
561	11439
562	9776
563	9133
564	9306
565	10700
566	11607
567	9856
568	7627
569	6568
570	8703
571	11638
572	13841
573	14351
574	14991
575	14905
576	12230
577	10062
578	9423
579	10537
580	11634
581	10533
582	8884
583	9570
584	11443
585	10342
586	7600
587	6811
588	7458
589	7841
590	7619
591	8302
592	10819
593	12041
594	10167
595	7837
596	7919
597	8349
598	8210
599	8914
600	10167
601	10806
602	11137
603	10510
604	9808
605	8983
606	9469
607	10959
608	9686
609	7862
610	9439
611	11193
612	9827
613	7862
614	8291
615	10451
616	12128
617	12205
618	12426
619	12443
620	11411
621	11109
622	11475
623	11508
624	9460
625	8009
626	8212
627	9565
628	10756
629	9201
630	7948
631	9499
632	10689
633	9476
634	8165
635	8391
636	9147
637	9164
638	9662
639	9782
640	8371
641	7729
642	8064
643	8329
644	8547
645	8242
646	8565
647	10416
648	10867
649	10563
650	10433
651	8675
652	8248
653	7820
654	7073
655	6805
656	7372
657	7440
658	6893
659	7616
660	9096
661	9797
662	10561
663	10016
664	9179
665	8934
666	7886
667	6886
668	7617
669	8010
670	7441
671	7220
672	6944
673	6438
674	5392
675	4239
676	3647
677	4047
678	5990
679	8333
680	7929
681	7260
682	6985
683	5999
684	6327
685	7309
686	7523
687	7915
688	7669
689	8595
690	10259
691	9339
692	6777
693	5329
694	4880
695	5543
696	7563
697	7793
698	6415
699	6653
700	8620
701	8744
702	7434
703	8465
704	9503
705	9800
706	9090
707	6971
708	6800
709	7246
710	7341
711	7837
712	8552
713	9416
714	11031
715	12111
716	10005
717	8208
718	9168
719	11503
720	13423
721	12551
722	11230
723	11015
724	11896
725	10942
726	8728
727	9135
728	9515
729	8673
730	8465
731	9996
732	12597
733	11747
734	10056
735	9246
736	8947
737	9227
738	9046
739	10330
740	12021
741	13041
742	13776
743	11720
744	9327
745	8961
746	9467
747	11381
748	13451
749	13364
750	12006
751	12062
752	14628
753	16585
754	18866
755	18376
756	14305
757	9885
758	9312
759	10162
760	11218
761	12109
762	11316
763	10520
764	11117
765	12241
766	13143
767	11754
768	12685
769	14962
770	12772
771	9958
772	9561
773	10459
774	11481
775	11669
776	11352
777	11318
778	11388
779	11620
780	11557
781	10677
782	11351
783	12874
784	14353
785	13099
786	9831
787	8892
788	9013
789	9778
790	11433
791	12744
792	17488
793	18437
794	16141
795	16258
796	15016
797	14238
798	14048
799	12778
800	12259
801	13602
802	15458
803	14805
804	12754
805	10651
806	12463
807	14867
808	14886
809	14870
810	14505
811	13965
812	12647
813	12709
814	12811
815	12722
816	11039
817	7563
818	7060
819	9962
820	14184
821	15082
822	16007
823	17315
824	13202
825	12310
826	13271
827	13238
828	12335
829	12847
830	13147
831	13171
832	13748
833	11559
834	9376
835	9957
836	9311
837	9824
838	10821
839	10197
840	11564
841	12671
842	12935
843	9990
844	7890
845	9372
846	13557
847	14936
848	13872
849	13158
850	13672
851	14298
852	14186
853	12707
854	10153
855	10104
856	9798
857	8544
858	8167
859	6610
860	6933
861	9485
862	9270
863	8577
864	9316
865	9216
866	10120
867	8484
868	7671
869	7350
870	6549
871	6773
872	6813
873	6931
874	7394
875	8317
876	5853
877	4038
878	5223
879	8906
880	9420
881	6631
882	7064
883	8229
884	7613
885	7074
886	5617
887	4158
888	5253
889	6159
890	4578
891	5279
892	6204
893	5211
894	2749
895	3235
896	5219
897	5264
898	5576
899	8148
900	10024
901	7224
902	5516
903	4275
904	4445
905	4384
906	5888
907	7192
908	5726
909	6012
910	5561
911	4498
912	3045
913	3499
914	3196
915	2749
916	4779
917	4187
918	3577
919	4142
920	5861
921	5561
922	4993
923	7392
924	8034
925	6861
926	5384
927	4914
928	5205
929	5790
930	5341
931	5831
932	5528
933	4288
934	2638
935	2341
936	2999
937	6194
938	7409
939	5612
940	6772
941	6329
942	5294
943	4352
944	3870
945	3156
946	4258
947	5048
948	5565
949	4221
950	2572
951	2313
952	4380
953	6649
954	5569
955	4750
956	4844
957	5380
958	4999
959	5149
960	4863
961	5231
962	4924
963	3945
964	4269
965	4431
966	3461
967	3872
968	3356
969	3575
970	5251
971	5432
972	4810
973	6465
974	6316
975	4372
976	4174
977	5845
978	5690
979	5271
980	5605
981	4277
982	3686
983	3597
984	5777
985	6724
986	3555
987	3076
988	3298
989	4005
990	4074
991	3185
992	3402
993	4193
994	4259
995	4449
996	4275
997	3878
998	5128
999	5728
1000	4704
1001	3230
1002	3804
1003	4218
1004	4341
1005	5172
1006	6657
1007	7277
1008	6752
1009	5388
1010	4526
1011	4396
1012	5265
1013	4895
1014	3090
1015	3414
1016	3572
1017	2916
1018	3174
1019	4867
1020	3572
1021	1943
1022	2480
1023	3851
1024	3831