1	12069
2	12726
3	12887
4	12099
5	10886
6	9823
7	9409
8	9413
9	9926
10	10484
11	11912
12	13503
13	15039
14	15030
15	14065
16	13322
17	12736
18	13158
19	13864
20	14346
21	15649
22	16660
23	16892
24	16596
25	15999
26	15214
27	14316
28	13276
29	13176
30	13742
31	14717
32	14983
33	14954
34	13677
35	12031
36	10264
37	9201
38	9065
39	10179
40	11926
41	13851
42	14998
43	14458
44	12685
45	11401
46	10769
47	10932
48	11400
49	12408
50	12684
51	12741
52	12259
53	11927
54	11377
55	10754
56	10714
57	11478
58	12083
59	12325
60	12062
61	11805
62	11942
63	12267
64	12330
65	12054
66	12679
67	12771
68	12668
69	11590
70	10668
71	10420
72	9966
73	10215
74	11193
75	13397
76	15562
77	16949
78	17400
79	16550
80	14741
81	12425
82	10110
83	8597
84	8905
85	10821
86	13671
87	16483
88	18203
89	17926
90	16497
91	15134
92	14335
93	14500
94	14653
95	14691
96	15198
97	15703
98	15127
99	13940
100	12273
101	10673
102	10339
103	10916
104	11488
105	11560
106	12043
107	12784
108	13489
109	13772
110	14398
111	14872
112	14694
113	13572
114	12663
115	12194
116	12645
117	13768
118	15823
119	17455
120	17565
121	16499
122	14451
123	12630
124	11921
125	12187
126	13059
127	13998
128	14929
129	15563
130	16266
131	16354
132	16513
133	16226
134	15298
135	14217
136	13160
137	12862
138	13049
139	12130
140	11265
141	10969
142	11003
143	10357
144	9245
145	9556
146	11303
147	13253
148	14178
149	13885
150	13551
151	13772
152	14310
153	14134
154	14164
155	14225
156	13916
157	12363
158	10079
159	8745
160	8429
161	9520
162	11239
163	13203
164	14786
165	15116
166	15086
167	14611
168	13486
169	12244
170	11824
171	12088
172	12343
173	12397
174	11745
175	11636
176	11984
177	12683
178	13494
179	14499
180	14671
181	13713
182	13140
183	13620
184	14501
185	14571
186	14233
187	13668
188	13005
189	12364
190	12031
191	12013
192	11890
193	12374
194	13543
195	14500
196	14955
197	14540
198	13505
199	13302
200	13099
201	13376
202	13801
203	14771
204	15184
205	14318
206	12449
207	10264
208	8111
209	7721
210	8932
211	11139
212	13675
213	15910
214	17005
215	16483
216	14612
217	12492
218	11318
219	11609
220	12598
221	13222
222	12468
223	10949
224	9373
225	10042
226	12184
227	14067
228	14311
229	13856
230	13720
231	14180
232	14470
233	14086
234	13397
235	13273
236	14078
237	14576
238	14044
239	12296
240	11590
241	11686
242	11998
243	12129
244	12146
245	12512
246	12911
247	13410
248	14689
249	15584
250	15923
251	15437
252	14545
253	14654
254	16295
255	17996
256	19232
257	18818
258	17354
259	16583
260	15600
261	14809
262	13990
263	13326
264	12927
265	12416
266	11586
267	11229
268	12449
269	14241
270	15029
271	15857
272	16103
273	16061
274	15607
275	14988
276	14354
277	14041
278	14526
279	14946
280	14776
281	14553
282	15750
283	16515
284	17335
285	17592
286	18214
287	19384
288	19547
289	17840
290	14662
291	12922
292	12804
293	14453
294	17131
295	18339
296	18009
297	16300
298	15302
299	15499
300	16696
301	18064
302	18313
303	17613
304	16518
305	15348
306	13447
307	12026
308	12275
309	13209
310	13981
311	12944
312	12578
313	14048
314	15929
315	15946
316	13752
317	12033
318	10801
319	9829
320	9504
321	10374
322	10828
323	11296
324	12078
325	13586
326	14734
327	15226
328	14158
329	12627
330	12208
331	13023
332	14635
333	16389
334	17707
335	18341
336	17327
337	15750
338	14600
339	14347
340	14751
341	15893
342	16594
343	16675
344	16385
345	15181
346	14189
347	15026
348	16669
349	17697
350	18380
351	19854
352	21317
353	21640
354	19965
355	17903
356	16672
357	17118
358	19237
359	20956
360	20547
361	18209
362	15344
363	13960
364	14476
365	16018
366	16831
367	15717
368	15086
369	14372
370	14644
371	15690
372	16760
373	18115
374	18778
375	18901
376	17658
377	15848
378	14746
379	14118
380	14055
381	14397
382	15482
383	15661
384	15168
385	15159
386	15824
387	16487
388	15965
389	16040
390	17645
391	18314
392	17222
393	14789
394	12610
395	12691
396	14679
397	17839
398	19805
399	20164
400	20520
401	21469
402	23692
403	25345
404	24791
405	22600
406	19420
407	16739
408	16053
409	16354
410	16170
411	14097
412	12626
413	11865
414	12786
415	15117
416	17304
417	18146
418	18501
419	17737
420	16048
421	15864
422	17301
423	17887
424	17373
425	17383
426	17991
427	18253
428	18514
429	17518
430	16327
431	15807
432	16514
433	18910
434	20280
435	21137
436	22200
437	22120
438	21794
439	21378
440	20313
441	18099
442	16590
443	17234
444	20252
445	21549
446	20676
447	18264
448	18339
449	20552
450	21884
451	22153
452	23361
453	24873
454	25144
455	23654
456	22556
457	22129
458	22041
459	20971
460	18560
461	17928
462	19050
463	21348
464	23743
465	25480
466	24755
467	23481
468	22019
469	21067
470	19712
471	19992
472	21228
473	23157
474	25320
475	26438
476	26458
477	26890
478	27369
479	27003
480	24579
481	22697
482	23741
483	25684
484	26171
485	26199
486	25986
487	26226
488	26495
489	24504
490	21402
491	20931
492	23425
493	27867
494	31093
495	34053
496	34513
497	31575
498	31881
499	33212
500	33055
501	31133
502	30085
503	31056
504	31765
505	33646
506	37038
507	36972
508	35768
509	37837
510	40705
511	37742
512	33468
513	31387
514	30376
515	31302
516	31418
517	28865
518	28758
519	31176
520	33445
521	32981
522	33723
523	34495
524	35042
525	36273
526	37625
527	40957
528	44317
529	43370
530	39139
531	38051
532	37222
533	33986
534	32326
535	34853
536	38837
537	40337
538	39212
539	41296
540	46976
541	53207
542	55662
543	55050
544	50919
545	48342
546	45445
547	43285
548	43381
549	44088
550	45617
551	47207
552	46479
553	45680
554	47634
555	50431
556	52644
557	54391
558	53996
559	55564
560	55961
561	50571
562	47142
563	49901
564	54553
565	57882
566	62121
567	63554
568	64894
569	68617
570	70249
571	70537
572	74006
573	74600
574	71308
575	69241
576	64044
577	61255
578	63437
579	63736
580	65405
581	70219
582	74779
583	77253
584	80498
585	83360
586	85939
587	89900
588	92373
589	97473
590	100629
591	104967
592	106321
593	100522
594	95885
595	96797
596	99277
597	98566
598	101056
599	102857
600	103735
601	110207
602	121496
603	131495
604	131820
605	128726
606	128169
607	126919
608	125922
609	132591
610	141229
611	148227
612	154497
613	153739
614	149093
615	142763
616	135032
617	137568
618	144608
619	151314
620	146205
621	149037
622	162554
623	172594
624	179491
625	184078
626	185632
627	188691
628	198577
629	194485
630	185833
631	189350
632	199529
633	210290
634	212759
635	206177
636	211878
637	220150
638	219329
639	215632
640	210906
641	208467
642	203212
643	195999
644	192054
645	199740
646	198674
647	191419
648	199681
649	215685
650	226959
651	225422
652	219504
653	217975
654	219722
655	219785
656	212202
657	201628
658	197387
659	200468
660	209119
661	213688
662	211749
663	204762
664	195634
665	196423
666	193101
667	180990
668	175985
669	176754
670	182418
671	188378
672	194146
673	190709
674	184002
675	172477
676	161983
677	160909
678	161929
679	160426
680	158980
681	156131
682	155328
683	153537
684	143258
685	137571
686	135375
687	136830
688	129561
689	127322
690	125644
691	118185
692	115633
693	119307
694	121120
695	119428
696	115445
697	109579
698	103911
699	98408
700	91771
701	87598
702	89341
703	96087
704	104436
705	102666
706	101288
707	98777
708	89838
709	81912
710	75765
711	74235
712	76195
713	76134
714	73535
715	67995
716	67010
717	71326
718	75917
719	77220
720	72432
721	68722
722	68553
723	66840
724	61744
725	55661
726	57060
727	60571
728	62891
729	63504
730	63080
731	60670
732	53151
733	48146
734	45958
735	51405
736	56369
737	53887
738	49652
739	51391
740	52674
741	53416
742	52842
743	49428
744	46435
745	46746
746	48976
747	52999
748	52293
749	49822
750	50507
751	53590
752	50888
753	44935
754	44957
755	46809
756	45448
757	44667
758	43295
759	44804
760	43757
761	43826
762	38328
763	32483
764	32553
765	37361
766	47001
767	51267
768	48569
769	45313
770	44294
771	43025
772	41946
773	38461
774	36057
775	40057
776	42778
777	38859
778	34903
779	38454
780	41737
781	39882
782	35613
783	33399
784	34249
785	36742
786	34167
787	33779
788	37489
789	39994
790	39092
791	34865
792	31412
793	29425
794	30577
795	32599
796	34232
797	35047
798	33382
799	32300
800	30919
801	32197
802	33332
803	32782
804	31447
805	26678
806	21875
807	25097
808	29935
809	32152
810	30523
811	29391
812	28905
813	28122
814	30898
815	34973
816	33859
817	33478
818	34549
819	34841
820	34189
821	31185
822	26805
823	25684
824	25120
825	26277
826	32021
827	31326
828	28155
829	26572
830	25896
831	25237
832	25848
833	23148
834	23907
835	26269
836	26027
837	23330
838	22391
839	22298
840	19843
841	15831
842	15045
843	17564
844	19711
845	21567
846	26032
847	26103
848	23024
849	19944
850	18573
851	19655
852	18964
853	19774
854	17921
855	14044
856	15280
857	17446
858	16960
859	18082
860	17517
861	17531
862	19823
863	19994
864	19678
865	22389
866	21443
867	18045
868	16994
869	16011
870	17389
871	18309
872	17784
873	17120
874	17163
875	18241
876	16594
877	14805
878	15952
879	16258
880	19099
881	22317
882	20929
883	17027
884	16594
885	17201
886	17347
887	15860
888	19004
889	20615
890	20462
891	17358
892	14696
893	14944
894	14166
895	12943
896	12817
897	14486
898	16864
899	16410
900	14843
901	14585
902	14896
903	13220
904	12523
905	12623
906	15027
907	16117
908	16404
909	15506
910	14164
911	17379
912	17151
913	16602
914	13748
915	8871
916	9531
917	13352
918	15538
919	13703
920	13293
921	15998
922	15125
923	11456
924	14369
925	13806
926	13295
927	14037
928	11740
929	11364
930	15939
931	14921
932	13584
933	12510
934	16191
935	21070
936	17131
937	14436
938	13513
939	11818
940	14124
941	16648
942	18482
943	15101
944	11173
945	12339
946	13576
947	12997
948	14619
949	17843
950	19744
951	22138
952	20502
953	16828
954	12083
955	10378
956	14231
957	16743
958	16119
959	11218
960	9633
961	11073
962	14163
963	16687
964	12639
965	9512
966	9890
967	12146
968	11346
969	12591
970	11967
971	9683
972	10341
973	11864
974	11649
975	8813
976	11571
977	12255
978	10416
979	11143
980	12163
981	13418
982	11621
983	11317
984	11390
985	13593
986	14559
987	15045
988	14475
989	18908
990	19895
991	13273
992	11748
993	9985
994	10871
995	12186
996	9535
997	11190
998	12521
999	11090
1000	10298
1001	8383
1002	11456
1003	13937
1004	11491
1005	12656
1006	12910
1007	11333
1008	13260
1009	12785
1010	9990
1011	9729
1012	11868
1013	10231
1014	8461
1015	7249
1016	8487
1017	8675
1018	10276
1019	13951
1020	18916
1021	16212
1022	10738
1023	9864
1024	12562