1	12168
2	12334
3	12495
4	11808
5	10835
6	9577
7	9311
8	9999
9	11053
10	12059
11	12818
12	13050
13	12712
14	12326
15	11735
16	11707
17	11925
18	12196
19	12085
20	11601
21	11437
22	11591
23	11855
24	11756
25	11964
26	12093
27	11661
28	10589
29	9518
30	8857
31	8993
32	9455
33	10309
34	10220
35	9651
36	8430
37	7772
38	7887
39	8799
40	9339
41	9960
42	10591
43	10574
44	10409
45	10396
46	10114
47	10550
48	10893
49	10996
50	10398
51	10356
52	10577
53	10719
54	10167
55	8741
56	7479
57	7027
58	7216
59	7612
60	7908
61	7791
62	7935
63	8199
64	8334
65	8874
66	9519
67	10043
68	10257
69	10174
70	9807
71	9433
72	8981
73	8724
74	8722
75	8737
76	8921
77	9448
78	10146
79	10683
80	10477
81	10114
82	9821
83	9646
84	9751
85	9894
86	10042
87	10053
88	10790
89	11298
90	11670
91	11557
92	10655
93	9928
94	9345
95	9421
96	10625
97	12622
98	14232
99	14963
100	14920
101	13927
102	13453
103	13569
104	13202
105	12616
106	12270
107	12211
108	12341
109	11843
110	11446
111	11509
112	11914
113	11986
114	11477
115	10852
116	10020
117	9361
118	8918
119	8403
120	8114
121	7835
122	7467
123	7581
124	7820
125	8637
126	9549
127	10794
128	12233
129	13164
130	13146
131	11815
132	11058
133	11226
134	11312
135	10928
136	10186
137	9179
138	8382
139	8243
140	9157
141	10395
142	11275
143	11528
144	10769
145	9671
146	8567
147	7783
148	7669
149	8099
150	8220
151	8465
152	9126
153	10106
154	11193
155	11485
156	11230
157	9896
158	8602
159	8103
160	8396
161	8981
162	9619
163	10197
164	11074
165	10961
166	10677
167	9731
168	9149
169	9337
170	9681
171	10430
172	10606
173	10766
174	11352
175	12658
176	13649
177	13425
178	12717
179	11711
180	10147
181	8105
182	7072
183	7677
184	8553
185	8899
186	8924
187	9161
188	9649
189	9959
190	9628
191	9306
192	8979
193	9457
194	10615
195	11626
196	12095
197	11481
198	10199
199	10122
200	10947
201	12499
202	12967
203	12523
204	12196
205	11706
206	11091
207	10614
208	10344
209	10971
210	11648
211	11449
212	11202
213	11367
214	12196
215	13593
216	14764
217	15601
218	15501
219	14788
220	13799
221	13899
222	14880
223	15472
224	14809
225	13781
226	12404
227	11517
228	11057
229	10947
230	10214
231	8566
232	7165
233	6660
234	6978
235	7261
236	7401
237	7138
238	6580
239	6387
240	6720
241	7218
242	7731
243	8235
244	8850
245	9335
246	10340
247	10909
248	10908
249	10882
250	10877
251	10834
252	10070
253	9430
254	9272
255	8820
256	7864
257	7300
258	7834
259	9619
260	10996
261	11097
262	10652
263	10111
264	9729
265	10025
266	11014
267	11947
268	12867
269	13273
270	13316
271	13881
272	13491
273	12232
274	11443
275	11009
276	10927
277	10919
278	11377
279	11722
280	12289
281	12822
282	13363
283	13280
284	13292
285	13533
286	13677
287	13758
288	13067
289	12765
290	11525
291	10746
292	11616
293	14445
294	16823
295	16912
296	15450
297	13420
298	12070
299	10546
300	9533
301	9509
302	9668
303	10025
304	10619
305	11628
306	11354
307	10192
308	9345
309	8209
310	8104
311	8791
312	9993
313	11336
314	11751
315	11554
316	11563
317	12561
318	13377
319	13018
320	11488
321	10619
322	11253
323	12143
324	12479
325	13418
326	14562
327	14693
328	14057
329	13717
330	14320
331	14781
332	15164
333	14789
334	14496
335	14853
336	15466
337	14375
338	12629
339	11979
340	11996
341	11535
342	10541
343	9217
344	8783
345	10179
346	11923
347	13349
348	13605
349	13758
350	13378
351	13119
352	12850
353	12569
354	12115
355	11638
356	11865
357	12581
358	12540
359	11672
360	10993
361	10536
362	11064
363	12599
364	13626
365	12640
366	10533
367	9262
368	8257
369	7751
370	7765
371	7567
372	7145
373	6992
374	7303
375	8405
376	9237
377	9265
378	9400
379	9258
380	9730
381	10400
382	11611
383	12110
384	11559
385	10562
386	9962
387	11208
388	13214
389	14656
390	14673
391	14042
392	13481
393	14610
394	15227
395	14597
396	13349
397	12505
398	11639
399	11021
400	11677
401	12824
402	13390
403	13282
404	13490
405	13090
406	12284
407	11439
408	11586
409	12532
410	13070
411	12494
412	11875
413	10962
414	10497
415	10604
416	11622
417	12394
418	12681
419	12662
420	12839
421	13605
422	14586
423	15029
424	14273
425	13933
426	13404
427	12855
428	12618
429	13546
430	15719
431	16845
432	16886
433	15798
434	13125
435	11253
436	9427
437	8385
438	8234
439	8764
440	9489
441	9957
442	10425
443	11309
444	12745
445	12948
446	13184
447	14391
448	14946
449	14819
450	14905
451	13837
452	12211
453	12436
454	13565
455	12941
456	13748
457	16649
458	18720
459	17703
460	15996
461	15552
462	15746
463	16637
464	17230
465	17459
466	17065
467	16856
468	15078
469	13382
470	12771
471	13743
472	15851
473	17985
474	18643
475	16759
476	15128
477	15482
478	15745
479	14067
480	12656
481	12341
482	13219
483	14642
484	15361
485	15651
486	17858
487	19515
488	18897
489	17193
490	15381
491	12807
492	11489
493	13724
494	17406
495	19712
496	18318
497	15507
498	13598
499	13692
500	15228
501	16581
502	16922
503	15236
504	13705
505	14152
506	16736
507	18456
508	17650
509	17455
510	18107
511	18261
512	17248
513	16295
514	16681
515	18490
516	20658
517	22342
518	23247
519	22401
520	21568
521	20021
522	18715
523	19009
524	19875
525	19167
526	18999
527	19865
528	18770
529	17676
530	16945
531	16379
532	16381
533	16289
534	14950
535	16303
536	19799
537	21141
538	21556
539	23005
540	23189
541	22263
542	20977
543	20460
544	20101
545	19539
546	18487
547	19498
548	21604
549	21943
550	21386
551	19905
552	16957
553	15719
554	17798
555	20873
556	22442
557	21704
558	19200
559	16958
560	16044
561	18266
562	19744
563	20018
564	23525
565	25497
566	25017
567	23605
568	22170
569	20030
570	18095
571	18606
572	21795
573	26776
574	30623
575	29835
576	25728
577	23258
578	23763
579	26574
580	29762
581	29499
582	26470
583	24200
584	24796
585	26659
586	26297
587	26048
588	25404
589	25595
590	28214
591	32616
592	32921
593	29815
594	29485
595	31225
596	30586
597	26458
598	27070
599	30735
600	32246
601	30925
602	29955
603	29088
604	26246
605	25795
606	29076
607	31468
608	31494
609	33094
610	33521
611	32286
612	32328
613	33788
614	34810
615	30344
616	24085
617	24205
618	29889
619	36036
620	38072
621	36366
622	34479
623	34200
624	33357
625	32943
626	33638
627	32750
628	34201
629	36561
630	38861
631	37706
632	35911
633	39025
634	39713
635	39147
636	40929
637	41944
638	42066
639	43083
640	42035
641	38839
642	35593
643	31714
644	31014
645	36051
646	38222
647	40771
648	47578
649	48735
650	47507
651	46500
652	48110
653	50328
654	45646
655	38359
656	32208
657	31091
658	33790
659	35548
660	34055
661	33355
662	35955
663	35513
664	31873
665	30870
666	32869
667	34324
668	36584
669	40816
670	40799
671	40814
672	41036
673	39627
674	44480
675	47533
676	43068
677	39102
678	39923
679	37923
680	37263
681	37409
682	34264
683	32117
684	30379
685	31730
686	32745
687	31401
688	27075
689	25741
690	28863
691	31816
692	33228
693	32975
694	30037
695	30915
696	31792
697	28078
698	24204
699	21575
700	22170
701	23436
702	25192
703	24769
704	20403
705	18177
706	20174
707	24328
708	26432
709	24317
710	21910
711	19167
712	20642
713	24279
714	24623
715	26421
716	23627
717	19097
718	19910
719	22539
720	22093
721	22065
722	22489
723	20263
724	18685
725	19110
726	19997
727	21108
728	20125
729	17332
730	15514
731	17597
732	17919
733	17915
734	19873
735	21863
736	18487
737	16414
738	14592
739	14825
740	16850
741	16767
742	16433
743	19003
744	22476
745	20930
746	21066
747	23603
748	22401
749	19508
750	19650
751	19852
752	18701
753	19075
754	20526
755	20632
756	18402
757	18630
758	17087
759	17833
760	17842
761	18254
762	20197
763	19379
764	16048
765	14241
766	15458
767	15297
768	15463
769	16801
770	15725
771	16170
772	15949
773	14237
774	15117
775	16958
776	16658
777	15858
778	16924
779	18712
780	17801
781	17026
782	16267
783	15275
784	14696
785	15662
786	15743
787	15185
788	15938
789	15357
790	13057
791	15880
792	18813
793	18499
794	17066
795	15133
796	13884
797	17289
798	21511
799	18548
800	14203
801	13844
802	16387
803	17977
804	16986
805	17924
806	18365
807	16240
808	11060
809	8583
810	11130
811	14043
812	12586
813	11423
814	11814
815	14918
816	16400
817	16429
818	16032
819	15679
820	15415
821	16083
822	13540
823	11040
824	14830
825	15808
826	14264
827	13162
828	12162
829	13052
830	12475
831	14432
832	17552
833	16243
834	14180
835	14312
836	15743
837	15443
838	14715
839	13913
840	12375
841	12468
842	10890
843	9782
844	10478
845	12942
846	13270
847	11634
848	12702
849	14110
850	13724
851	12661
852	12533
853	12089
854	11129
855	10059
856	10760
857	11415
858	12405
859	14764
860	13760
861	14162
862	13810
863	13287
864	12390
865	10936
866	10759
867	10350
868	11756
869	12417
870	11656
871	9724
872	8745
873	9417
874	9534
875	10370
876	12004
877	10008
878	11010
879	10478
880	7856
881	7296
882	9405
883	9722
884	8066
885	8859
886	10696
887	11386
888	11498
889	10768
890	12980
891	14541
892	13884
893	14645
894	15724
895	13697
896	10596
897	11035
898	12582
899	12094
900	9996
901	8734
902	10513
903	12964
904	11638
905	11184
906	12462
907	12723
908	12404
909	12448
910	9788
911	10363
912	13601
913	12233
914	9245
915	9129
916	11276
917	9881
918	8314
919	9230
920	9619
921	8182
922	9955
923	10447
924	9158
925	10121
926	11297
927	12220
928	11971
929	7939
930	7295
931	11810
932	14136
933	12236
934	11706
935	11928
936	12202
937	11267
938	11468
939	12082
940	10905
941	9675
942	8869
943	10266
944	11435
945	7292
946	6291
947	11167
948	12051
949	11983
950	13425
951	12774
952	10714
953	8745
954	8263
955	7769
956	7403
957	9274
958	10067
959	10275
960	10329
961	8777
962	9964
963	16102
964	16890
965	14290
966	14808
967	12302
968	11843
969	10133
970	10497
971	11063
972	8374
973	8639
974	12795
975	11467
976	8584
977	9141
978	7679
979	6465
980	7061
981	9116
982	10913
983	9616
984	8840
985	6771
986	6020
987	4607
988	5738
989	8954
990	10188
991	12096
992	13980
993	12542
994	12472
995	13816
996	10397
997	7791
998	8885
999	9847
1000	9024
1001	7734
1002	7288
1003	9918
1004	7750
1005	8110
1006	10707
1007	12386
1008	12554
1009	10658
1010	9998
1011	9575
1012	11269
1013	8484
1014	6292
1015	7337
1016	7902
1017	7508
1018	6104
1019	8022
1020	8792
1021	9299
1022	7894
1023	6257
1024	5837