1	11916
2	11483
3	10701
4	9672
5	9136
6	9249
7	10024
8	10507
9	10665
10	10707
11	10767
12	10819
13	11224
14	10571
15	9991
16	9291
17	9211
18	9455
19	10081
20	10828
21	11494
22	11329
23	10720
24	9967
25	9535
26	10056
27	10373
28	10711
29	10441
30	10354
31	10556
32	10876
33	11169
34	11030
35	10817
36	10486
37	10371
38	10837
39	11512
40	12582
41	12837
42	12134
43	10539
44	9466
45	9514
46	10204
47	11413
48	12470
49	13029
50	12470
51	11963
52	11228
53	10818
54	10602
55	10755
56	11135
57	11523
58	11115
59	10919
60	11033
61	10654
62	10492
63	10977
64	11693
65	12127
66	12061
67	11803
68	11719
69	11771
70	11794
71	11364
72	11222
73	11065
74	11163
75	11359
76	12484
77	13436
78	13950
79	14035
80	14228
81	14198
82	14110
83	13708
84	13078
85	13435
86	14655
87	15859
88	16357
89	15197
90	14346
91	13746
92	14278
93	14905
94	15476
95	16641
96	17217
97	17209
98	16207
99	15085
100	14045
101	13259
102	13474
103	13507
104	13256
105	12654
106	12347
107	12516
108	13089
109	12996
110	12580
111	11502
112	11021
113	11080
114	11977
115	12553
116	12591
117	12401
118	12254
119	12431
120	12510
121	13027
122	13184
123	13735
124	14497
125	15223
126	14988
127	14269
128	13751
129	12836
130	12477
131	12395
132	12042
133	11719
134	11397
135	12253
136	13134
137	13632
138	13401
139	12779
140	12361
141	12458
142	12330
143	12411
144	12696
145	13392
146	14285
147	14546
148	14506
149	14448
150	14407
151	14436
152	14935
153	14757
154	14873
155	14480
156	13505
157	12769
158	13040
159	13448
160	14006
161	14311
162	14656
163	15091
164	15847
165	15615
166	14857
167	14092
168	13862
169	13722
170	13329
171	12970
172	12394
173	12884
174	13389
175	13698
176	13533
177	13022
178	12809
179	12728
180	12759
181	13069
182	13448
183	13988
184	13984
185	14514
186	15095
187	15498
188	15375
189	14987
190	14045
191	13255
192	12637
193	12730
194	13185
195	13819
196	14337
197	14585
198	14208
199	13988
200	13572
201	14114
202	14606
203	14810
204	15175
205	15245
206	15549
207	16393
208	16910
209	16920
210	16430
211	15533
212	15038
213	15196
214	15092
215	15712
216	16524
217	17848
218	18934
219	19525
220	19656
221	19426
222	18176
223	16744
224	15464
225	15797
226	16036
227	16578
228	16534
229	16789
230	17184
231	16998
232	16286
233	15308
234	14596
235	14386
236	15112
237	16410
238	16780
239	16535
240	16010
241	15874
242	15690
243	16537
244	17274
245	17210
246	16576
247	16110
248	16152
249	16254
250	16220
251	16169
252	16792
253	17660
254	18357
255	18316
256	18328
257	18589
258	18629
259	18620
260	17173
261	15987
262	15394
263	15801
264	16473
265	16835
266	17218
267	18147
268	19391
269	20025
270	20162
271	20512
272	20651
273	20240
274	19988
275	19858
276	20034
277	20028
278	19951
279	19789
280	18854
281	18074
282	18717
283	19382
284	20240
285	20652
286	20554
287	20317
288	20557
289	21408
290	21181
291	20126
292	18462
293	17828
294	17707
295	17550
296	17747
297	17442
298	17607
299	17849
300	18179
301	18054
302	17949
303	17981
304	17901
305	18725
306	19730
307	20069
308	19680
309	20067
310	20493
311	20011
312	19572
313	19649
314	20720
315	22068
316	22279
317	22816
318	22900
319	22521
320	21489
321	20428
322	19340
323	19273
324	20672
325	22394
326	23820
327	23627
328	22236
329	21259
330	22104
331	22675
332	22498
333	22657
334	22595
335	23420
336	24570
337	25139
338	25511
339	25833
340	25912
341	25564
342	24484
343	23682
344	23574
345	24528
346	23938
347	23121
348	22735
349	24174
350	25873
351	26433
352	26159
353	26321
354	26066
355	24989
356	23551
357	23842
358	25660
359	27436
360	28388
361	28537
362	28169
363	28308
364	28327
365	27610
366	26883
367	26560
368	27233
369	27038
370	26106
371	26552
372	27250
373	27293
374	26496
375	27154
376	29260
377	29578
378	28485
379	27872
380	27862
381	27379
382	26116
383	25526
384	26600
385	28448
386	28763
387	27467
388	27504
389	28592
390	29673
391	29824
392	29205
393	27927
394	26493
395	25915
396	25958
397	26422
398	27407
399	28582
400	30157
401	32058
402	33207
403	33208
404	32237
405	30950
406	31063
407	31299
408	31833
409	32612
410	33258
411	32708
412	32364
413	32774
414	33380
415	33927
416	33553
417	33981
418	35271
419	37508
420	37628
421	36060
422	35078
423	35474
424	35605
425	34520
426	33771
427	34113
428	34749
429	34826
430	35585
431	35420
432	34520
433	34399
434	34356
435	33728
436	32127
437	31360
438	32444
439	34056
440	35900
441	37191
442	36413
443	36274
444	36827
445	37644
446	39152
447	40201
448	40414
449	38715
450	37406
451	38846
452	40928
453	42068
454	41447
455	40049
456	38369
457	37672
458	38038
459	37779
460	37509
461	38106
462	39295
463	40018
464	40051
465	40775
466	41767
467	42739
468	43670
469	45698
470	45149
471	44870
472	43733
473	43418
474	43540
475	45085
476	45825
477	43990
478	42822
479	43605
480	45697
481	47860
482	47374
483	45197
484	43233
485	44409
486	47507
487	50355
488	52622
489	51844
490	50573
491	48965
492	45869
493	44400
494	44089
495	46265
496	49236
497	51239
498	51970
499	50458
500	48440
501	48468
502	51385
503	53464
504	52584
505	49323
506	49350
507	53116
508	55543
509	54827
510	52908
511	51445
512	51659
513	51221
514	50838
515	51689
516	51539
517	51417
518	52048
519	51916
520	53497
521	55996
522	56818
523	57391
524	59586
525	58627
526	56371
527	56152
528	58574
529	60141
530	59936
531	58057
532	56155
533	56432
534	56707
535	58654
536	60674
537	62057
538	63649
539	63037
540	61038
541	59327
542	57675
543	58489
544	59904
545	62337
546	63748
547	63330
548	61861
549	61489
550	62323
551	63591
552	62531
553	60802
554	59751
555	59244
556	59456
557	62279
558	64420
559	67344
560	69762
561	65566
562	60910
563	58945
564	61344
565	63027
566	63229
567	65052
568	67256
569	65647
570	65023
571	67312
572	69254
573	66801
574	63219
575	63521
576	63322
577	62652
578	61752
579	60939
580	59169
581	58854
582	62558
583	65907
584	65682
585	64262
586	63835
587	64273
588	63890
589	62889
590	61727
591	61951
592	62647
593	62652
594	64059
595	66467
596	67258
597	63329
598	61833
599	63888
600	62705
601	60927
602	58599
603	58718
604	57782
605	57480
606	60411
607	62611
608	60791
609	59857
610	59525
611	57513
612	56035
613	53925
614	54159
615	55271
616	53810
617	55621
618	56402
619	54881
620	54985
621	57747
622	57854
623	56516
624	54327
625	53506
626	56251
627	57244
628	56877
629	55644
630	55342
631	53997
632	52460
633	55751
634	57294
635	57212
636	55811
637	56365
638	54920
639	52327
640	51937
641	51688
642	50057
643	50390
644	49320
645	50730
646	53138
647	52061
648	49740
649	46177
650	45810
651	48619
652	50455
653	49222
654	47248
655	47727
656	48673
657	48783
658	46652
659	44901
660	46329
661	46895
662	47371
663	46930
664	45790
665	46950
666	46301
667	45139
668	45365
669	44778
670	43180
671	41873
672	42309
673	44052
674	47522
675	46244
676	43681
677	42379
678	43066
679	43760
680	42017
681	40846
682	42140
683	42467
684	40551
685	39803
686	40876
687	43112
688	42687
689	40331
690	38662
691	37231
692	36010
693	35313
694	36353
695	37625
696	36416
697	34212
698	32099
699	30722
700	32331
701	35588
702	38661
703	39684
704	38240
705	37522
706	37041
707	35140
708	31713
709	31233
710	34431
711	36760
712	36106
713	34004
714	33115
715	35130
716	34910
717	31238
718	28643
719	27500
720	30664
721	35257
722	36612
723	35021
724	34397
725	33442
726	32028
727	31356
728	34211
729	35315
730	35377
731	34008
732	33130
733	33458
734	33515
735	32167
736	30398
737	30288
738	30218
739	29329
740	29368
741	29022
742	31343
743	32487
744	31096
745	29810
746	29326
747	29384
748	28323
749	28250
750	29178
751	27886
752	25611
753	25597
754	26931
755	27009
756	25150
757	25366
758	26232
759	27523
760	28460
761	27487
762	26346
763	25658
764	24694
765	25397
766	26356
767	27786
768	28093
769	26752
770	26295
771	26078
772	26219
773	25928
774	27264
775	28176
776	26205
777	28392
778	29192
779	28262
780	29210
781	25840
782	24009
783	23356
784	22229
785	23098
786	26514
787	26809
788	25105
789	25821
790	25503
791	24516
792	22673
793	21176
794	21002
795	23588
796	24880
797	24761
798	25935
799	25149
800	24465
801	23398
802	22221
803	21980
804	21596
805	20586
806	20706
807	23497
808	26222
809	24744
810	22809
811	23956
812	23496
813	22958
814	21797
815	21362
816	21322
817	21831
818	19788
819	21250
820	23258
821	24292
822	26335
823	26801
824	24792
825	23465
826	22613
827	21714
828	21213
829	21156
830	20557
831	22045
832	22694
833	22181
834	22922
835	22805
836	23431
837	22826
838	22600
839	22892
840	22271
841	21676
842	21530
843	20317
844	20399
845	21698
846	21199
847	20457
848	18678
849	19346
850	21528
851	21394
852	20239
853	21447
854	20752
855	22320
856	23643
857	20545
858	20129
859	20334
860	19687
861	21002
862	20881
863	19563
864	18381
865	18091
866	19272
867	18415
868	19753
869	21417
870	20375
871	18782
872	18291
873	19114
874	19322
875	19766
876	20273
877	19039
878	18122
879	18167
880	18685
881	18462
882	18313
883	17706
884	16790
885	19186
886	20393
887	19951
888	18664
889	17951
890	16894
891	17371
892	18638
893	18659
894	17600
895	17920
896	19096
897	19467
898	20078
899	18182
900	15933
901	17590
902	19745
903	22146
904	19892
905	16725
906	18754
907	19438
908	18000
909	17183
910	17896
911	16210
912	15142
913	15823
914	18458
915	18595
916	15909
917	14371
918	15238
919	15588
920	15814
921	16146
922	16154
923	17335
924	18720
925	17488
926	15885
927	16041
928	15715
929	14609
930	15954
931	15431
932	13804
933	15707
934	16378
935	15563
936	17013
937	15861
938	13622
939	14220
940	14388
941	16271
942	17558
943	16874
944	17197
945	16682
946	18076
947	17384
948	13875
949	15266
950	17754
951	17283
952	16261
953	17168
954	17368
955	16479
956	16477
957	16729
958	17330
959	16638
960	14394
961	15135
962	17295
963	16246
964	14507
965	13943
966	15181
967	15155
968	15028
969	13418
970	14794
971	16780
972	15129
973	12807
974	13667
975	15043
976	16343
977	16437
978	17610
979	16526
980	14751
981	14868
982	14588
983	13751
984	14552
985	14752
986	13012
987	13448
988	13736
989	16445
990	16421
991	16833
992	16796
993	17064
994	15784
995	12802
996	11906
997	14209
998	14536
999	12916
1000	12621
1001	11849
1002	11395
1003	12288
1004	15226
1005	14727
1006	13151
1007	11810
1008	12470
1009	12302
1010	13922
1011	13047
1012	12295
1013	12931
1014	13628
1015	14225
1016	15402
1017	17237
1018	16696
1019	14822
1020	13516
1021	14730
1022	18706
1023	19852
1024	18663