1	14865
2	13875
3	13272
4	13427
5	14510
6	16083
7	17182
8	16700
9	15552
10	14150
11	13834
12	14583
13	15409
14	15758
15	15382
16	15001
17	14729
18	14847
19	14809
20	14769
21	14015
22	13308
23	12551
24	12403
25	13569
26	15047
27	16378
28	16574
29	15507
30	14598
31	14209
32	14203
33	14827
34	15266
35	15699
36	15994
37	15786
38	16059
39	16551
40	17658
41	19474
42	20835
43	20847
44	20856
45	21189
46	21385
47	21684
48	22329
49	22998
50	23309
51	22764
52	22168
53	22355
54	23303
55	24734
56	25639
57	26400
58	26682
59	26517
60	27754
61	29119
62	30870
63	32667
64	33234
65	33472
66	34521
67	35138
68	35206
69	34569
70	35121
71	37321
72	39978
73	41769
74	42862
75	43872
76	44903
77	46542
78	49276
79	52048
80	53964
81	54560
82	54357
83	54276
84	54700
85	54959
86	55101
87	55502
88	55589
89	56877
90	58743
91	59362
92	59607
93	58277
94	56033
95	54462
96	54621
97	55638
98	55963
99	55717
100	55165
101	52820
102	50267
103	47426
104	44305
105	41249
106	39145
107	37236
108	36674
109	35653
110	35992
111	36004
112	36507
113	36076
114	35315
115	34282
116	32513
117	30855
118	28725
119	27036
120	26081
121	26827
122	26302
123	25404
124	24340
125	24284
126	23500
127	22070
128	21039
129	21008
130	22006
131	22835
132	22991
133	22994
134	23337
135	23369
136	22514
137	21246
138	19480
139	18250
140	17922
141	17792
142	18071
143	18475
144	17862
145	16657
146	15352
147	15155
148	15513
149	15875
150	16026
151	16171
152	16952
153	18408
154	19462
155	19842
156	19418
157	18986
158	18481
159	17896
160	17490
161	17388
162	18408
163	18881
164	19279
165	18112
166	16871
167	15879
168	15482
169	15668
170	15884
171	16685
172	16275
173	15852
174	14841
175	13832
176	13541
177	13615
178	14277
179	14613
180	14959
181	15231
182	15474
183	15781
184	15826
185	15846
186	15507
187	15016
188	14239
189	13687
190	13403
191	13694
192	14484
193	15230
194	15467
195	15007
196	15051
197	15395
198	15523
199	14874
200	13569
201	13301
202	13538
203	13861
204	13804
205	14237
206	14852
207	16033
208	16831
209	17353
210	17438
211	17851
212	18220
213	18421
214	17640
215	16432
216	15356
217	14806
218	14704
219	14975
220	15669
221	16334
222	16916
223	17216
224	16167
225	14967
226	14135
227	14569
228	14558
229	14657
230	14531
231	15147
232	15611
233	16136
234	16171
235	16563
236	16676
237	16390
238	14813
239	13212
240	12781
241	13196
242	13557
243	13405
244	13268
245	12642
246	13171
247	13735
248	14061
249	14576
250	15867
251	17261
252	18168
253	17690
254	17210
255	18007
256	18811
257	18507
258	17502
259	17277
260	17295
261	17585
262	17235
263	16809
264	16655
265	16823
266	17644
267	18587
268	18985
269	18638
270	17567
271	17770
272	19150
273	19922
274	20048
275	19166
276	17621
277	16197
278	15573
279	15902
280	16175
281	15714
282	15460
283	15371
284	15772
285	15829
286	15861
287	16078
288	16930
289	17968
290	18241
291	17671
292	17040
293	17890
294	19197
295	19749
296	20130
297	20002
298	20297
299	21033
300	21121
301	21197
302	20944
303	20447
304	19729
305	19300
306	18671
307	18093
308	16960
309	16911
310	17575
311	18403
312	19823
313	20825
314	20645
315	19363
316	18071
317	17205
318	17143
319	17963
320	19125
321	19440
322	19882
323	19677
324	18672
325	17127
326	16987
327	17850
328	19254
329	19920
330	19825
331	19871
332	19968
333	20270
334	21151
335	21904
336	22589
337	22439
338	22472
339	22330
340	22167
341	21679
342	19853
343	18567
344	18544
345	19379
346	19884
347	20390
348	20627
349	20781
350	20197
351	19120
352	18408
353	18839
354	20211
355	20981
356	20559
357	20935
358	21492
359	21895
360	22588
361	22666
362	22960
363	23306
364	22871
365	22071
366	22797
367	24333
368	24620
369	22997
370	21914
371	21478
372	21175
373	20725
374	21120
375	22441
376	23762
377	23803
378	24125
379	24159
380	24828
381	24952
382	24812
383	23929
384	23613
385	23826
386	23421
387	23466
388	24868
389	25379
390	24647
391	23427
392	21936
393	20365
394	19394
395	19160
396	19964
397	20772
398	22377
399	24936
400	27018
401	26794
402	25952
403	25868
404	26725
405	27513
406	27327
407	26168
408	25980
409	24330
410	23283
411	22994
412	24277
413	26065
414	27693
415	27678
416	26022
417	23530
418	22366
419	23572
420	26478
421	27985
422	27494
423	26973
424	26424
425	25926
426	25413
427	24766
428	24919
429	26802
430	29467
431	31072
432	31025
433	31048
434	30606
435	29335
436	26860
437	25190
438	24189
439	24905
440	26345
441	27147
442	27618
443	28195
444	27856
445	26868
446	26800
447	27509
448	29689
449	31201
450	32133
451	32220
452	31525
453	29852
454	29074
455	30903
456	32090
457	31778
458	32005
459	33146
460	33374
461	32105
462	31121
463	29848
464	29743
465	31470
466	33636
467	33744
468	31885
469	30462
470	28680
471	27936
472	28014
473	28676
474	30545
475	33176
476	34789
477	35977
478	36092
479	34376
480	33635
481	34875
482	36701
483	37981
484	37982
485	36970
486	36484
487	36001
488	34918
489	32838
490	31756
491	32755
492	33626
493	35097
494	36070
495	37275
496	37503
497	36608
498	34844
499	33074
500	32856
501	33593
502	34161
503	35406
504	35810
505	35924
506	35267
507	34222
508	34158
509	35503
510	36267
511	35110
512	33689
513	32365
514	32769
515	34641
516	35853
517	36581
518	37409
519	37191
520	37355
521	36376
522	35651
523	36032
524	37558
525	37694
526	37703
527	37752
528	38556
529	39439
530	38851
531	36352
532	33592
533	32310
534	33110
535	35156
536	36763
537	37491
538	38451
539	38485
540	37496
541	37247
542	38668
543	39237
544	39340
545	39982
546	38500
547	36328
548	34823
549	34596
550	36739
551	37553
552	38120
553	38932
554	38595
555	37864
556	37501
557	39193
558	40408
559	40864
560	41967
561	40512
562	38609
563	38282
564	39352
565	39882
566	39309
567	37517
568	37780
569	36647
570	35428
571	34759
572	35761
573	37033
574	37663
575	37657
576	35566
577	34514
578	35431
579	37670
580	40197
581	40854
582	40143
583	39172
584	40173
585	41669
586	42214
587	42695
588	42927
589	43994
590	42888
591	40005
592	38006
593	36703
594	36104
595	36164
596	37846
597	38753
598	37858
599	36564
600	37067
601	37766
602	38973
603	39464
604	39199
605	38703
606	40378
607	42042
608	40538
609	38633
610	38255
611	38590
612	38338
613	38542
614	37818
615	38187
616	38535
617	37595
618	34769
619	32553
620	31186
621	31362
622	32728
623	33295
624	32605
625	32426
626	33005
627	32918
628	33356
629	33895
630	34814
631	34918
632	34648
633	34795
634	34383
635	34257
636	35627
637	38544
638	40007
639	37505
640	34213
641	32316
642	29094
643	26959
644	27342
645	30520
646	31637
647	30286
648	30232
649	30212
650	29235
651	27557
652	27088
653	28378
654	30191
655	31659
656	30642
657	30090
658	30879
659	31949
660	32474
661	31038
662	30995
663	31030
664	30406
665	27563
666	24882
667	24315
668	24833
669	28273
670	31310
671	29876
672	27992
673	28370
674	28388
675	27287
676	27420
677	27354
678	28169
679	28325
680	29259
681	29152
682	26926
683	23632
684	22066
685	24903
686	26093
687	26920
688	27971
689	26863
690	26387
691	27282
692	29053
693	29947
694	28532
695	29818
696	31573
697	28345
698	25433
699	25011
700	25304
701	25980
702	26993
703	28628
704	27834
705	24772
706	23266
707	23168
708	23411
709	24261
710	24779
711	26233
712	27561
713	26664
714	24572
715	24084
716	24313
717	23949
718	22750
719	21146
720	21413
721	22110
722	21521
723	19345
724	19412
725	21547
726	25814
727	26276
728	23545
729	23205
730	25119
731	28340
732	27959
733	25095
734	23694
735	24212
736	23033
737	21264
738	22257
739	23476
740	22125
741	21266
742	22362
743	23704
744	23910
745	22463
746	20957
747	21729
748	22296
749	22837
750	22918
751	21641
752	20280
753	19470
754	20266
755	20558
756	20255
757	21233
758	20962
759	21319
760	21071
761	23373
762	24964
763	24716
764	24292
765	24814
766	21967
767	19315
768	19909
769	21424
770	22484
771	22412
772	22502
773	21307
774	20712
775	21588
776	23796
777	25965
778	26751
779	25972
780	24516
781	23574
782	21196
783	19113
784	18808
785	19807
786	19716
787	19104
788	18326
789	18894
790	17569
791	15898
792	14948
793	17318
794	19481
795	20170
796	19180
797	18797
798	18014
799	17154
800	18001
801	19470
802	18291
803	17433
804	17869
805	18305
806	16888
807	16901
808	19171
809	20029
810	19512
811	19214
812	20117
813	18001
814	18165
815	20001
816	21309
817	22369
818	21627
819	20469
820	20186
821	20297
822	18619
823	16631
824	17699
825	17608
826	16226
827	15446
828	15713
829	16799
830	17230
831	17154
832	17047
833	17607
834	18116
835	17956
836	16919
837	16694
838	15515
839	15987
840	17145
841	18104
842	19740
843	19020
844	18024
845	14790
846	14029
847	15915
848	16691
849	15151
850	14342
851	14275
852	14625
853	17206
854	19202
855	18556
856	19172
857	19118
858	16157
859	15698
860	15666
861	14786
862	16505
863	15276
864	13949
865	15274
866	17389
867	16774
868	15575
869	14448
870	14575
871	17744
872	19956
873	18976
874	15912
875	16225
876	18216
877	18966
878	18004
879	15231
880	16366
881	18205
882	17049
883	14898
884	14941
885	15729
886	13644
887	13879
888	16144
889	16553
890	15615
891	14175
892	14587
893	16383
894	16846
895	15422
896	15936
897	16522
898	14920
899	12986
900	13226
901	14561
902	14882
903	14521
904	15267
905	15790
906	14438
907	15471
908	16490
909	15745
910	14137
911	14445
912	13658
913	12083
914	14010
915	13996
916	15195
917	14621
918	14096
919	13658
920	13455
921	14971
922	13921
923	12256
924	11373
925	11830
926	14096
927	14566
928	15364
929	13888
930	13311
931	14974
932	14401
933	13965
934	13988
935	14761
936	15922
937	15070
938	12862
939	14749
940	15382
941	14326
942	14646
943	15420
944	15972
945	13924
946	14521
947	13985
948	14440
949	13607
950	11875
951	11945
952	11900
953	12600
954	12316
955	13085
956	16449
957	16373
958	14923
959	14439
960	14724
961	14286
962	13458
963	12273
964	13501
965	13919
966	13282
967	12258
968	12333
969	14180
970	14634
971	15357
972	16497
973	16475
974	14668
975	13981
976	13559
977	15194
978	16642
979	16636
980	14343
981	13870
982	14477
983	13783
984	11736
985	9852
986	10094
987	11727
988	12986
989	13485
990	12069
991	12339
992	14818
993	14400
994	13829
995	12648
996	12675
997	13842
998	11826
999	10812
1000	10516
1001	11823
1002	12001
1003	11789
1004	11900
1005	11308
1006	11954
1007	13316
1008	13772
1009	12882
1010	14496
1011	15614
1012	14723
1013	12307
1014	12537
1015	13436
1016	13687
1017	14191
1018	11776
1019	11970
1020	13634
1021	14212
1022	13167
1023	10992
1024	10916