1	9319
2	9147
3	8548
4	7573
5	6599
6	6096
7	6332
8	6701
9	6832
10	7344
11	7626
12	7846
13	7920
14	7068
15	6363
16	5950
17	6075
18	6417
19	6269
20	6056
21	5787
22	5759
23	5481
24	4906
25	4752
26	4886
27	5595
28	6203
29	6222
30	6318
31	6580
32	6697
33	6972
34	6968
35	7073
36	7299
37	7018
38	6666
39	6267
40	6482
41	6279
42	5783
43	4704
44	4208
45	4466
46	4434
47	4256
48	3960
49	4065
50	4562
51	4843
52	5485
53	6127
54	6654
55	6797
56	6167
57	5796
58	5228
59	5012
60	4952
61	4469
62	4131
63	4702
64	5350
65	5400
66	4787
67	4045
68	3609
69	3649
70	3406
71	3348
72	3364
73	3709
74	4141
75	4101
76	3641
77	3293
78	3429
79	4211
80	4894
81	5530
82	5748
83	6075
84	6514
85	7559
86	7991
87	7819
88	7323
89	6886
90	7590
91	8663
92	9351
93	9509
94	9354
95	8485
96	7279
97	6646
98	6607
99	7021
100	7573
101	7378
102	7104
103	6993
104	7246
105	6911
106	6499
107	5872
108	5212
109	5286
110	5956
111	6491
112	6654
113	6359
114	6000
115	6347
116	6541
117	6816
118	6395
119	6108
120	6009
121	6247
122	6370
123	6400
124	6847
125	8000
126	9093
127	9172
128	8352
129	7241
130	6378
131	5771
132	5465
133	5399
134	5528
135	5279
136	5528
137	6023
138	6244
139	5946
140	5417
141	5112
142	5274
143	5869
144	6965
145	8319
146	9115
147	8901
148	7824
149	6234
150	5227
151	4836
152	5435
153	5770
154	6217
155	6230
156	6231
157	6662
158	7512
159	8440
160	8955
161	8779
162	8695
163	8200
164	8657
165	9318
166	10099
167	10494
168	10866
169	10846
170	10950
171	11910
172	12418
173	12270
174	12200
175	12646
176	14753
177	16679
178	17583
179	16756
180	15638
181	14463
182	14070
183	13544
184	12404
185	11033
186	10151
187	10071
188	10291
189	10320
190	10481
191	11916
192	12989
193	13312
194	12911
195	12955
196	12940
197	13727
198	14223
199	13708
200	12434
201	10431
202	10056
203	11022
204	12566
205	14722
206	17012
207	18478
208	18102
209	16606
210	14800
211	14761
212	16439
213	17333
214	15813
215	13736
216	13376
217	14812
218	16663
219	18333
220	18676
221	17962
222	15796
223	14211
224	12775
225	13284
226	14011
227	14930
228	15330
229	15950
230	16196
231	15383
232	14416
233	14042
234	14598
235	15675
236	17074
237	17689
238	16470
239	15194
240	14231
241	14283
242	13223
243	12031
244	12113
245	13271
246	13714
247	13328
248	13147
249	14065
250	15169
251	15804
252	16468
253	17614
254	18162
255	18461
256	18342
257	18441
258	17863
259	16753
260	14838
261	14467
262	15426
263	16485
264	16346
265	14432
266	13305
267	12889
268	13458
269	13869
270	12942
271	11564
272	10540
273	9554
274	9355
275	9443
276	10698
277	12218
278	12288
279	11897
280	11885
281	12779
282	13997
283	14246
284	13012
285	11487
286	10422
287	10969
288	11522
289	11675
290	11774
291	11489
292	10566
293	10710
294	11930
295	12808
296	13668
297	12906
298	11559
299	10876
300	11346
301	11346
302	11219
303	11303
304	11284
305	11076
306	11501
307	11950
308	12802
309	13222
310	13604
311	13060
312	12233
313	12145
314	12295
315	12210
316	11152
317	9691
318	8150
319	7348
320	7060
321	7975
322	10190
323	12126
324	12555
325	11169
326	9589
327	9522
328	10217
329	11724
330	13478
331	13763
332	12567
333	10377
334	8772
335	8348
336	8553
337	8893
338	9470
339	11039
340	13344
341	14725
342	13658
343	11877
344	11572
345	13286
346	13929
347	13950
348	14091
349	15082
350	15999
351	15102
352	13690
353	12164
354	11824
355	11911
356	11324
357	10388
358	9919
359	9377
360	9841
361	10572
362	11502
363	12341
364	12491
365	12431
366	12561
367	12676
368	13980
369	14171
370	13110
371	11824
372	10326
373	10503
374	12885
375	16460
376	18670
377	18393
378	17012
379	16248
380	17063
381	16794
382	15229
383	13086
384	12835
385	13212
386	13019
387	12602
388	12299
389	12220
390	13190
391	14384
392	14641
393	13799
394	12734
395	13303
396	15640
397	17506
398	18014
399	18055
400	18457
401	17428
402	16462
403	15863
404	16251
405	17389
406	19043
407	20090
408	20242
409	18165
410	15998
411	14749
412	14081
413	14892
414	17639
415	20665
416	23026
417	23137
418	21318
419	18870
420	17670
421	17050
422	16672
423	17561
424	18568
425	19019
426	19525
427	21362
428	23495
429	22473
430	20690
431	19050
432	18406
433	18807
434	19613
435	20136
436	19823
437	19459
438	19463
439	21237
440	22691
441	22078
442	19824
443	18112
444	17870
445	17826
446	18832
447	18532
448	18220
449	18977
450	20038
451	20618
452	21812
453	22248
454	20277
455	17965
456	18383
457	19666
458	20226
459	18844
460	18323
461	20777
462	20853
463	19278
464	18955
465	20292
466	21251
467	20623
468	17416
469	15621
470	15093
471	14832
472	14536
473	15112
474	18741
475	24142
476	27391
477	27538
478	25670
479	22662
480	20708
481	21334
482	21283
483	22097
484	22234
485	20284
486	18269
487	16734
488	18249
489	20597
490	22086
491	21899
492	21437
493	22769
494	23256
495	22627
496	20848
497	18478
498	20223
499	23223
500	23346
501	21374
502	19837
503	18856
504	18205
505	16631
506	14995
507	15485
508	16619
509	15847
510	15927
511	17517
512	18987
513	19385
514	18092
515	15038
516	13185
517	13436
518	16209
519	19771
520	20879
521	18077
522	14903
523	14180
524	15267
525	14710
526	12976
527	12844
528	13380
529	13041
530	13967
531	15772
532	16564
533	17002
534	15687
535	14296
536	14060
537	15194
538	16921
539	17750
540	17905
541	17877
542	16609
543	14692
544	13647
545	13207
546	13052
547	13605
548	12702
549	10382
550	9916
551	11318
552	11913
553	11602
554	12161
555	13185
556	12387
557	10722
558	9477
559	10147
560	11433
561	11933
562	12257
563	12320
564	11837
565	12014
566	14255
567	14107
568	12563
569	11896
570	10639
571	9398
572	10471
573	11069
574	9715
575	8911
576	9117
577	10358
578	11693
579	12414
580	13734
581	14908
582	13286
583	12016
584	13300
585	14530
586	13482
587	10667
588	10270
589	11304
590	11021
591	10786
592	11329
593	11854
594	12477
595	13078
596	13303
597	11602
598	8965
599	7495
600	6648
601	7337
602	9791
603	11738
604	12269
605	13485
606	13658
607	12740
608	13255
609	13969
610	13035
611	11073
612	11863
613	13334
614	12781
615	11789
616	10727
617	9126
618	7773
619	8653
620	10441
621	10319
622	8527
623	7996
624	10958
625	12619
626	11224
627	10446
628	9484
629	8682
630	9946
631	10466
632	10033
633	10875
634	11556
635	10922
636	8703
637	8387
638	10354
639	11511
640	9818
641	8623
642	8298
643	8634
644	8480
645	8022
646	8585
647	8427
648	7419
649	7523
650	10850
651	12957
652	11799
653	9681
654	8320
655	9156
656	11167
657	11468
658	9616
659	8526
660	8277
661	8002
662	7070
663	8087
664	8928
665	8049
666	6958
667	6923
668	7267
669	8169
670	9420
671	9995
672	8613
673	6613
674	6783
675	6384
676	5691
677	6758
678	7838
679	7066
680	7685
681	8726
682	8816
683	8836
684	9216
685	9670
686	8694
687	8810
688	9491
689	9885
690	10575
691	9486
692	8473
693	8716
694	6735
695	5299
696	7132
697	8997
698	10729
699	12218
700	11437
701	10372
702	9515
703	7998
704	9847
705	12777
706	11426
707	9186
708	7226
709	8258
710	9929
711	11530
712	12909
713	12676
714	11042
715	8292
716	6683
717	7308
718	8526
719	8233
720	7823
721	8465
722	10866
723	12949
724	13404
725	12897
726	12329
727	10432
728	8956
729	8447
730	8816
731	9676
732	13231
733	14295
734	11868
735	11184
736	10998
737	11609
738	12857
739	14448
740	15338
741	15314
742	14293
743	12855
744	12575
745	15598
746	14607
747	12361
748	12559
749	11598
750	11557
751	14041
752	15554
753	13275
754	13750
755	14484
756	12462
757	12620
758	13365
759	12703
760	13738
761	16256
762	12804
763	12181
764	12828
765	10518
766	10227
767	11644
768	12743
769	14020
770	16125
771	17533
772	15164
773	13627
774	12993
775	13794
776	14235
777	14101
778	12930
779	13496
780	13054
781	13478
782	15082
783	15468
784	16648
785	14495
786	13652
787	14484
788	15240
789	15665
790	18169
791	22160
792	18527
793	14611
794	12159
795	10821
796	12678
797	14538
798	16010
799	12413
800	10848
801	11233
802	11385
803	12693
804	11492
805	10327
806	10350
807	11860
808	15254
809	15212
810	13547
811	13927
812	15181
813	15990
814	14475
815	12118
816	13539
817	14135
818	15038
819	14094
820	13769
821	15428
822	17120
823	14819
824	13849
825	15792
826	12672
827	10595
828	12314
829	13115
830	15538
831	16857
832	17798
833	19147
834	15808
835	13728
836	14664
837	14706
838	12263
839	8795
840	10194
841	11263
842	10116
843	9664
844	11167
845	13084
846	13268
847	11184
848	11855
849	10091
850	8514
851	10081
852	11942
853	10563
854	9769
855	8681
856	9366
857	9678
858	8656
859	7948
860	9913
861	10786
862	8074
863	6735
864	7912
865	11053
866	12407
867	11149
868	11635
869	11011
870	9678
871	8411
872	6645
873	7228
874	9056
875	9782
876	8621
877	7676
878	8594
879	8976
880	7653
881	6709
882	6996
883	6202
884	6531
885	7502
886	6493
887	5237
888	5161
889	6020
890	8146
891	10865
892	12256
893	8517
894	7300
895	9531
896	8435
897	8562
898	9692
899	8635
900	8740
901	8004
902	7329
903	10473
904	9429
905	7645
906	8142
907	9226
908	8170
909	7715
910	8454
911	6120
912	5651
913	7203
914	6938
915	5287
916	4569
917	4395
918	4580
919	6301
920	6518
921	5133
922	5072
923	6587
924	5815
925	4761
926	4956
927	6407
928	7389
929	6859
930	8252
931	8643
932	8748
933	7664
934	8519
935	8788
936	9327
937	7902
938	6167
939	5761
940	4532
941	4048
942	3881
943	2490
944	3430
945	7264
946	9125
947	8852
948	7958
949	4865
950	3905
951	5035
952	4499
953	3858
954	4807
955	6195
956	5769
957	4140
958	3989
959	6228
960	9657
961	8127
962	5111
963	2761
964	2500
965	3080
966	3692
967	4814
968	6263
969	5461
970	4762
971	4887
972	3373
973	4808
974	5044
975	4769
976	5302
977	5164
978	7052
979	6881
980	5600
981	6037
982	6652
983	6772
984	5848
985	3708
986	2065
987	2906
988	5479
989	6484
990	4877
991	2647
992	2746
993	3304
994	4024
995	4227
996	3676
997	5629
998	8259
999	6395
1000	5174
1001	5116
1002	6703
1003	7918
1004	7615
1005	7106
1006	11330
1007	9637
1008	5700
1009	6219
1010	5805
1011	3970
1012	3573
1013	4375
1014	6784
1015	4790
1016	3550
1017	3600
1018	4281
1019	5872
1020	4783
1021	2680
1022	3012
1023	4339
1024	5029