1	12617
2	12187
3	12432
4	12301
5	12363
6	12184
7	12059
8	11682
9	11455
10	11331
11	11728
12	11959
13	12654
14	12790
15	12778
16	12648
17	12438
18	12521
19	12556
20	12674
21	12853
22	12719
23	12591
24	12550
25	12232
26	12192
27	12249
28	12616
29	12470
30	12879
31	12922
32	13566
33	13769
34	14008
35	14125
36	14220
37	13849
38	13636
39	13717
40	13645
41	14017
42	14296
43	14162
44	13570
45	13830
46	13740
47	13549
48	13562
49	13556
50	13653
51	13788
52	13732
53	13908
54	13798
55	13745
56	13924
57	14263
58	14428
59	14374
60	14538
61	14847
62	15034
63	15183
64	15203
65	15436
66	15294
67	15450
68	15697
69	15691
70	16066
71	16890
72	16891
73	17193
74	17679
75	18805
76	19845
77	20157
78	20448
79	21215
80	21838
81	22218
82	23103
83	24264
84	25917
85	27457
86	29620
87	31767
88	33548
89	35885
90	38889
91	42851
92	46901
93	49776
94	52359
95	53334
96	53799
97	53571
98	54230
99	54337
100	54534
101	51867
102	50340
103	48129
104	44863
105	42113
106	38272
107	35457
108	33102
109	30864
110	29907
111	28136
112	26675
113	24863
114	22989
115	21428
116	20179
117	19725
118	19427
119	19216
120	18653
121	18246
122	17910
123	17443
124	17377
125	17098
126	17119
127	16695
128	16534
129	16455
130	16370
131	15785
132	14780
133	14184
134	13792
135	13890
136	13569
137	12705
138	12499
139	11946
140	12065
141	11845
142	12228
143	12684
144	12799
145	12865
146	12595
147	12384
148	12954
149	13294
150	13949
151	14168
152	13925
153	13383
154	13877
155	14027
156	14213
157	14302
158	13816
159	13992
160	13433
161	13664
162	13992
163	13875
164	14220
165	14095
166	14528
167	14457
168	14262
169	14105
170	14206
171	13851
172	13588
173	13686
174	13522
175	13468
176	13892
177	14298
178	15003
179	14889
180	14067
181	13464
182	13667
183	13827
184	13907
185	14254
186	14696
187	14749
188	14362
189	13678
190	12997
191	12624
192	12619
193	13277
194	13892
195	14840
196	15004
197	14709
198	13567
199	13185
200	13437
201	13989
202	14281
203	13940
204	13527
205	14227
206	14514
207	14575
208	14515
209	14645
210	14974
211	15153
212	15892
213	16014
214	16867
215	17240
216	17603
217	17669
218	17954
219	18941
220	19363
221	19752
222	20551
223	22337
224	24186
225	25463
226	25924
227	26827
228	27706
229	28620
230	30409
231	32618
232	34409
233	34725
234	33890
235	33881
236	33698
237	33210
238	32563
239	31227
240	30835
241	30255
242	29071
243	27157
244	25060
245	23717
246	23538
247	23152
248	22085
249	20235
250	18922
251	17695
252	17060
253	16377
254	16411
255	16147
256	16130
257	16722
258	17095
259	17860
260	17950
261	17266
262	17180
263	16597
264	16557
265	16500
266	16594
267	16076
268	16103
269	15875
270	16244
271	16957
272	17235
273	17225
274	16443
275	16125
276	15219
277	14578
278	13811
279	13522
280	13703
281	13783
282	13870
283	14178
284	14713
285	14920
286	14963
287	15072
288	14853
289	14719
290	14516
291	15139
292	15609
293	15772
294	15550
295	15237
296	14891
297	15273
298	16153
299	16906
300	17767
301	18083
302	18529
303	18582
304	18748
305	18945
306	18446
307	18157
308	17731
309	16997
310	16056
311	14946
312	14711
313	15143
314	15732
315	15772
316	15465
317	14591
318	14104
319	14163
320	14745
321	14846
322	15042
323	14981
324	15247
325	15664
326	15700
327	15670
328	15317
329	15478
330	16330
331	17289
332	17887
333	18976
334	19517
335	19604
336	19810
337	20494
338	21113
339	21401
340	21537
341	21240
342	21224
343	20772
344	20742
345	20744
346	20619
347	20315
348	19885
349	18996
350	18258
351	18124
352	17936
353	17915
354	17917
355	17496
356	17305
357	16965
358	16968
359	16729
360	16530
361	15608
362	14771
363	14476
364	14834
365	15311
366	15472
367	14761
368	14468
369	14360
370	13840
371	13564
372	13939
373	14271
374	14320
375	14421
376	14838
377	15041
378	15059
379	15066
380	15880
381	16370
382	16373
383	16216
384	15495
385	15469
386	14976
387	14710
388	14583
389	15446
390	15583
391	15158
392	14830
393	14846
394	14915
395	14743
396	14559
397	14439
398	14710
399	14423
400	14194
401	14361
402	15308
403	15933
404	15886
405	15977
406	16379
407	15801
408	14997
409	14248
410	14705
411	14671
412	14334
413	14174
414	14214
415	14680
416	14918
417	14803
418	14606
419	14386
420	14377
421	14284
422	14529
423	14503
424	14784
425	14085
426	14193
427	15161
428	16605
429	16977
430	16232
431	15054
432	14363
433	14251
434	14422
435	14632
436	15011
437	15014
438	14428
439	13544
440	13996
441	14060
442	13953
443	13654
444	13437
445	13799
446	14175
447	14142
448	14195
449	14641
450	14802
451	14310
452	14189
453	13765
454	13876
455	14303
456	14364
457	13996
458	13618
459	13633
460	14407
461	15317
462	15803
463	16181
464	16140
465	15801
466	15728
467	15856
468	16283
469	17542
470	17542
471	17394
472	17119
473	17710
474	17796
475	18289
476	18715
477	18951
478	18935
479	18604
480	18269
481	18415
482	17945
483	17532
484	17260
485	17360
486	17689
487	17322
488	16907
489	16128
490	15775
491	16153
492	16901
493	16691
494	15855
495	15504
496	15702
497	14915
498	14472
499	14559
500	14390
501	14245
502	13952
503	13955
504	14205
505	15007
506	15765
507	15820
508	15646
509	15870
510	16355
511	16210
512	16056
513	16669
514	17096
515	17142
516	16787
517	16483
518	15600
519	14650
520	14642
521	15208
522	15461
523	15109
524	14683
525	14383
526	14437
527	14588
528	14821
529	15127
530	15238
531	15681
532	16156
533	16407
534	16008
535	16116
536	17102
537	17510
538	17192
539	16606
540	16443
541	16302
542	16345
543	16356
544	16651
545	17382
546	17283
547	17301
548	17200
549	16970
550	17195
551	17577
552	16987
553	16773
554	16597
555	15753
556	16034
557	17306
558	18689
559	18718
560	18641
561	18018
562	18204
563	18228
564	19091
565	19588
566	19701
567	19487
568	19327
569	18778
570	18128
571	17759
572	17450
573	17771
574	18976
575	20553
576	20973
577	21197
578	20958
579	21070
580	20577
581	20239
582	20064
583	19884
584	19846
585	20145
586	21209
587	21633
588	21706
589	21395
590	20374
591	19606
592	19876
593	20507
594	21284
595	22524
596	23670
597	24238
598	25266
599	25384
600	24430
601	23285
602	22122
603	22245
604	22855
605	23220
606	24969
607	26516
608	25684
609	24121
610	22698
611	22424
612	23202
613	24552
614	25507
615	26867
616	27198
617	27061
618	26892
619	27193
620	27141
621	27410
622	28122
623	28922
624	29540
625	29902
626	29030
627	28626
628	30165
629	30500
630	30068
631	30943
632	31974
633	33290
634	35189
635	35323
636	34449
637	33276
638	32465
639	34380
640	35994
641	36626
642	35662
643	36693
644	37112
645	36503
646	36721
647	37547
648	39068
649	41367
650	44870
651	46972
652	46315
653	45420
654	46217
655	47765
656	46708
657	48554
658	51065
659	53018
660	52812
661	51657
662	54014
663	56686
664	58543
665	58635
666	59058
667	60004
668	62406
669	65395
670	67710
671	68602
672	69367
673	70908
674	73856
675	74646
676	77863
677	81025
678	83418
679	83837
680	84251
681	86758
682	89330
683	92842
684	95512
685	99680
686	104361
687	107116
688	109454
689	110544
690	115463
691	115200
692	112333
693	114227
694	119548
695	122140
696	124584
697	123648
698	122258
699	123334
700	123408
701	122695
702	128286
703	133871
704	137261
705	139205
706	140895
707	137442
708	133100
709	132222
710	131750
711	134399
712	135875
713	138306
714	139358
715	141799
716	140019
717	137028
718	136140
719	137152
720	138229
721	140703
722	139776
723	133415
724	131270
725	133139
726	133705
727	129977
728	128298
729	124320
730	120899
731	116994
732	114348
733	113201
734	110210
735	108464
736	106463
737	101243
738	95909
739	92946
740	91445
741	89622
742	89785
743	85880
744	82657
745	79240
746	77244
747	75306
748	75945
749	74378
750	72073
751	70922
752	69148
753	67344
754	67324
755	67485
756	64945
757	63925
758	62136
759	61078
760	60229
761	59192
762	59733
763	60638
764	59044
765	60222
766	62705
767	61377
768	58439
769	55534
770	54505
771	52979
772	52931
773	54594
774	55103
775	54632
776	50917
777	48932
778	50666
779	53582
780	54197
781	52467
782	52816
783	53901
784	52175
785	49183
786	47419
787	47030
788	47554
789	48313
790	48104
791	48406
792	47502
793	46183
794	44195
795	45842
796	48670
797	49715
798	47950
799	45526
800	45678
801	48241
802	51485
803	52195
804	50967
805	49482
806	49138
807	49075
808	48924
809	48762
810	49232
811	49755
812	48663
813	47527
814	49739
815	51303
816	50558
817	47852
818	47725
819	48942
820	49028
821	49267
822	49799
823	49559
824	51108
825	53991
826	52597
827	49812
828	49340
829	48708
830	46374
831	48457
832	48654
833	47161
834	45940
835	43990
836	44326
837	46272
838	48824
839	47685
840	43218
841	40569
842	40473
843	40064
844	38639
845	37733
846	37838
847	38698
848	37508
849	36359
850	34726
851	34239
852	34333
853	33951
854	32541
855	30929
856	33252
857	33998
858	31587
859	29494
860	28452
861	28926
862	28535
863	28999
864	27715
865	26856
866	27184
867	27573
868	27639
869	27772
870	27366
871	26906
872	27532
873	27604
874	27355
875	26648
876	27024
877	25954
878	24636
879	24284
880	24344
881	23983
882	22365
883	20878
884	22119
885	23747
886	23627
887	24473
888	25152
889	24021
890	24751
891	23442
892	21406
893	21975
894	23132
895	23575
896	22251
897	21556
898	22045
899	20820
900	20178
901	20169
902	20438
903	20860
904	20831
905	22489
906	23910
907	22280
908	22589
909	22401
910	22203
911	23077
912	23656
913	24056
914	21825
915	21796
916	21557
917	19816
918	20507
919	21361
920	20203
921	20434
922	21873
923	21211
924	19577
925	20062
926	21302
927	21540
928	19110
929	18019
930	18098
931	19393
932	20824
933	20105
934	19776
935	19436
936	19204
937	19896
938	19121
939	19253
940	20853
941	21602
942	20485
943	20118
944	20983
945	19975
946	19654
947	20380
948	19974
949	20764
950	21670
951	22630
952	22094
953	22024
954	22592
955	21428
956	23151
957	24109
958	21280
959	21542
960	22790
961	23241
962	23618
963	22230
964	21061
965	20551
966	19623
967	20543
968	21864
969	21695
970	21592
971	22239
972	21659
973	20663
974	21376
975	22238
976	21869
977	21117
978	21476
979	22387
980	20823
981	18965
982	19130
983	18795
984	18188
985	17928
986	18161
987	18476
988	17955
989	17134
990	16331
991	17838
992	17252
993	16231
994	16081
995	16081
996	15890
997	16962
998	19007
999	18662
1000	17836
1001	18400
1002	17866
1003	17075
1004	16447
1005	16050
1006	16432
1007	15973
1008	16980
1009	16048
1010	15366
1011	15221
1012	15426
1013	15979
1014	16307
1015	16642
1016	17587
1017	17232
1018	15464
1019	15954
1020	17351
1021	16230
1022	15712
1023	16441
1024	16568