1	16964
2	16592
3	16000
4	15446
5	15991
6	16611
7	17653
8	18325
9	18901
10	19009
11	18530
12	17977
13	17878
14	17594
15	17261
16	17805
17	18445
18	19880
19	20918
20	21367
21	21034
22	20175
23	19551
24	19290
25	19849
26	19662
27	19271
28	18655
29	17138
30	16291
31	16170
32	16579
33	16917
34	16385
35	15377
36	15440
37	15831
38	16407
39	17294
40	18472
41	19493
42	20601
43	19001
44	16656
45	16066
46	16749
47	19183
48	21740
49	23194
50	22223
51	19948
52	17413
53	16490
54	17649
55	19686
56	21868
57	22746
58	22370
59	20872
60	20406
61	20769
62	21057
63	21792
64	22168
65	23198
66	24365
67	24379
68	24706
69	24515
70	24335
71	24281
72	23202
73	22891
74	23238
75	22983
76	22257
77	21975
78	21676
79	20864
80	19973
81	20400
82	21426
83	22680
84	23958
85	25589
86	27986
87	29102
88	29438
89	28016
90	26882
91	26540
92	27280
93	27726
94	27021
95	25975
96	24348
97	22610
98	21768
99	22543
100	24558
101	26749
102	29360
103	32269
104	33903
105	34648
106	34543
107	34913
108	35327
109	36357
110	39543
111	42786
112	44053
113	42197
114	39877
115	38493
116	41475
117	45703
118	49285
119	50539
120	50871
121	52101
122	53385
123	53695
124	54405
125	55914
126	57345
127	60046
128	65070
129	69878
130	76133
131	82223
132	87274
133	92222
134	94477
135	96380
136	98142
137	101149
138	102774
139	102876
140	105492
141	105366
142	102479
143	96941
144	91710
145	87968
146	85079
147	81503
148	82118
149	82839
150	83636
151	81877
152	78023
153	72433
154	69797
155	69186
156	69605
157	65577
158	60111
159	56103
160	53839
161	52164
162	49707
163	45426
164	41324
165	38026
166	36700
167	35720
168	35558
169	34687
170	33321
171	33319
172	33927
173	34559
174	34594
175	34875
176	35795
177	36274
178	36890
179	36364
180	36221
181	35796
182	35246
183	33286
184	31095
185	28769
186	27346
187	27443
188	29561
189	32998
190	35612
191	36185
192	33294
193	29166
194	26736
195	26472
196	27302
197	27530
198	26806
199	25443
200	23367
201	22128
202	22151
203	22765
204	23612
205	24692
206	24884
207	25523
208	24579
209	23257
210	21878
211	22152
212	23840
213	25175
214	25948
215	24870
216	23159
217	21496
218	20916
219	21547
220	22091
221	22426
222	21395
223	20870
224	20718
225	22940
226	24416
227	25233
228	25559
229	25008
230	24994
231	25204
232	24415
233	22466
234	21399
235	21165
236	21935
237	22275
238	22589
239	22495
240	21554
241	20221
242	20023
243	21918
244	24257
245	26321
246	28721
247	29948
248	29586
249	28055
250	25580
251	23517
252	21159
253	19603
254	18822
255	18392
256	18576
257	19336
258	21210
259	24775
260	27334
261	28816
262	27883
263	24789
264	22495
265	21721
266	22824
267	23750
268	23854
269	23441
270	22426
271	22539
272	23432
273	23971
274	23806
275	22774
276	20164
277	18127
278	17698
279	18945
280	19164
281	19499
282	21195
283	23611
284	25574
285	26649
286	27276
287	29337
288	30398
289	30110
290	27948
291	25730
292	24533
293	24031
294	22675
295	20710
296	19476
297	19319
298	19871
299	20385
300	21720
301	23939
302	25399
303	25686
304	25889
305	26357
306	26854
307	28042
308	29610
309	30678
310	28947
311	26537
312	25921
313	27033
314	28067
315	28586
316	29004
317	30065
318	31184
319	32722
320	34295
321	34338
322	34874
323	35771
324	36602
325	36897
326	37339
327	39474
328	41374
329	44303
330	46540
331	48193
332	49797
333	51243
334	49881
335	49025
336	50889
337	54501
338	55689
339	53522
340	52885
341	54628
342	57960
343	58579
344	56254
345	55727
346	59178
347	64230
348	64890
349	61672
350	57604
351	55684
352	54345
353	51560
354	51233
355	53053
356	55847
357	57266
358	58287
359	57453
360	56926
361	53935
362	51588
363	47924
364	46174
365	46602
366	47281
367	47729
368	49029
369	51156
370	53283
371	53565
372	51506
373	50987
374	51362
375	50939
376	47290
377	44659
378	43627
379	44215
380	47026
381	49001
382	47032
383	44995
384	45975
385	47251
386	47229
387	45049
388	43045
389	41664
390	42052
391	42325
392	41254
393	40510
394	39186
395	38559
396	39152
397	40068
398	41584
399	44134
400	46522
401	47717
402	47521
403	47448
404	47988
405	49927
406	50931
407	50196
408	49468
409	49163
410	49977
411	48980
412	48828
413	48410
414	44984
415	40620
416	40305
417	42607
418	45342
419	46360
420	48827
421	52522
422	54627
423	56733
424	60365
425	63322
426	65136
427	67030
428	68388
429	64554
430	63082
431	64714
432	66183
433	64978
434	64484
435	65251
436	62075
437	60362
438	66072
439	73799
440	74476
441	70034
442	68793
443	71220
444	73749
445	74586
446	75044
447	75400
448	74199
449	70421
450	67856
451	67492
452	70122
453	72841
454	74830
455	70915
456	65754
457	66484
458	71494
459	73480
460	70589
461	69948
462	73543
463	75673
464	75085
465	76900
466	79928
467	83752
468	87714
469	88925
470	84908
471	83900
472	83450
473	91226
474	99311
475	102465
476	105871
477	113540
478	119605
479	119578
480	116474
481	115793
482	120406
483	126302
484	126568
485	123164
486	124774
487	130185
488	137822
489	143112
490	148084
491	153078
492	158798
493	171078
494	183395
495	188124
496	185664
497	180380
498	180401
499	183588
500	184926
501	187443
502	195405
503	202563
504	199698
505	189788
506	191259
507	207789
508	223320
509	218427
510	205493
511	200567
512	207922
513	218001
514	221638
515	220898
516	213542
517	208769
518	217369
519	223819
520	230585
521	233916
522	237684
523	242613
524	251489
525	263979
526	269460
527	274716
528	288473
529	304920
530	300892
531	293817
532	297863
533	302897
534	304482
535	312555
536	332982
537	354893
538	366434
539	365443
540	373033
541	388897
542	396838
543	405682
544	423366
545	436425
546	430386
547	428421
548	432653
549	437633
550	450674
551	461010
552	468937
553	471041
554	484885
555	502594
556	504879
557	517876
558	532543
559	539496
560	544140
561	538244
562	547024
563	557052
564	564305
565	553504
566	550557
567	544182
568	536704
569	524814
570	517987
571	507382
572	496944
573	484612
574	469239
575	468691
576	462533
577	455372
578	452655
579	458380
580	466021
581	456601
582	452331
583	457491
584	456337
585	460789
586	466377
587	476761
588	480536
589	488398
590	506068
591	539774
592	560273
593	558702
594	563498
595	582385
596	599447
597	582965
598	563348
599	567000
600	574851
601	580569
602	577989
603	572511
604	551270
605	527486
606	498999
607	481000
608	464665
609	442781
610	428072
611	417362
612	402416
613	391959
614	382594
615	369462
616	343731
617	318596
618	297185
619	286406
620	284078
621	277813
622	252691
623	230677
624	232279
625	230908
626	220027
627	207497
628	204580
629	199238
630	192178
631	186978
632	183345
633	180624
634	176054
635	168465
636	169937
637	175214
638	169771
639	156037
640	145770
641	140914
642	141967
643	147767
644	145039
645	141689
646	135300
647	131129
648	136308
649	133428
650	125789
651	123611
652	122679
653	121305
654	120036
655	118789
656	125652
657	129896
658	124531
659	127610
660	134021
661	136468
662	137805
663	136397
664	139229
665	143098
666	143126
667	140287
668	137124
669	137112
670	132596
671	130314
672	135284
673	139878
674	134895
675	123929
676	120864
677	129756
678	130870
679	120798
680	117225
681	120151
682	121244
683	122555
684	124686
685	125775
686	122781
687	114891
688	105365
689	101440
690	101682
691	101143
692	99806
693	93715
694	92836
695	91745
696	89658
697	86105
698	82518
699	79286
700	80152
701	81624
702	77676
703	72961
704	80463
705	89278
706	89875
707	86072
708	78115
709	73890
710	77178
711	79582
712	77966
713	77307
714	79278
715	79959
716	73869
717	64741
718	64882
719	64050
720	61166
721	61050
722	59875
723	55776
724	55128
725	55042
726	55808
727	56268
728	57181
729	54886
730	50466
731	54964
732	62507
733	64161
734	57869
735	54192
736	52270
737	48827
738	48647
739	55128
740	56259
741	53386
742	58097
743	61058
744	59739
745	60990
746	59553
747	60009
748	63751
749	59927
750	58261
751	59867
752	58697
753	59525
754	56506
755	48388
756	48014
757	53174
758	52641
759	46880
760	40464
761	44682
762	47281
763	42684
764	36233
765	33808
766	34232
767	37239
768	42051
769	42915
770	39613
771	40884
772	40221
773	35284
774	30523
775	31998
776	35607
777	33360
778	30519
779	32461
780	33697
781	33541
782	32863
783	29610
784	27100
785	27741
786	29654
787	26904
788	22648
789	26951
790	32099
791	34018
792	31056
793	26646
794	24075
795	24032
796	23474
797	25702
798	27513
799	28806
800	24797
801	21687
802	25072
803	31170
804	26537
805	21237
806	22094
807	22432
808	20576
809	24363
810	26901
811	25191
812	21409
813	21166
814	23835
815	27779
816	31959
817	28495
818	20512
819	18099
820	21164
821	26995
822	27796
823	27561
824	27451
825	23330
826	21764
827	21355
828	19215
829	19205
830	19561
831	19910
832	18895
833	17980
834	21537
835	23574
836	21048
837	20174
838	19725
839	20658
840	22326
841	21138
842	22559
843	20560
844	17316
845	18953
846	18665
847	18112
848	20664
849	23300
850	21122
851	20646
852	17849
853	16899
854	16863
855	19096
856	23126
857	24166
858	20426
859	20475
860	20196
861	20982
862	20540
863	20291
864	19914
865	19162
866	18693
867	18184
868	19655
869	22411
870	22883
871	24269
872	24780
873	21062
874	19802
875	21199
876	22284
877	19525
878	17548
879	20557
880	20364
881	21975
882	22504
883	20730
884	17977
885	17750
886	17084
887	16705
888	16717
889	17633
890	18091
891	22477
892	23367
893	18941
894	18730
895	20312
896	21831
897	19653
898	16492
899	15261
900	13970
901	15761
902	19723
903	26368
904	30467
905	28711
906	26507
907	21527
908	19636
909	20943
910	20676
911	19704
912	18522
913	19477
914	21698
915	23360
916	21383
917	18850
918	15525
919	16981
920	20916
921	18694
922	17148
923	16348
924	17798
925	19479
926	18792
927	18147
928	18879
929	21757
930	21386
931	18525
932	17977
933	15698
934	15801
935	18571
936	21722
937	22289
938	21678
939	18275
940	12569
941	11399
942	14924
943	16050
944	16238
945	19837
946	18324
947	15304
948	15549
949	18539
950	18746
951	18091
952	15851
953	18226
954	22252
955	21412
956	17966
957	17532
958	18812
959	19188
960	15350
961	19046
962	27298
963	27341
964	24686
965	26478
966	24365
967	21716
968	19594
969	19180
970	21254
971	20481
972	15864
973	15353
974	20071
975	22731
976	22298
977	21277
978	19140
979	17190
980	18720
981	19667
982	21417
983	20585
984	16704
985	18218
986	22294
987	21761
988	20598
989	26040
990	23045
991	17602
992	17680
993	15864
994	16407
995	19024
996	21099
997	20530
998	18955
999	20904
1000	18116
1001	16671
1002	17306
1003	16356
1004	15100
1005	12710
1006	11562
1007	13584
1008	15643
1009	18378
1010	18083
1011	15208
1012	13656
1013	13346
1014	14094
1015	16485
1016	19201
1017	21623
1018	19718
1019	18893
1020	16631
1021	17469
1022	17682
1023	19094
1024	20093