1	11872
2	12196
3	12616
4	12508
5	12432
6	12267
7	12186
8	12084
9	12056
10	12019
11	12037
12	12185
13	12385
14	12530
15	12964
16	13317
17	13061
18	12385
19	12004
20	12043
21	12525
22	13172
23	13520
24	13200
25	12541
26	12038
27	11562
28	11757
29	11866
30	12290
31	12692
32	12628
33	12488
34	12267
35	12513
36	12908
37	12998
38	12943
39	13012
40	12835
41	12955
42	13237
43	13038
44	12864
45	13316
46	13149
47	13003
48	13005
49	13011
50	13111
51	13468
52	13650
53	14248
54	14116
55	13964
56	13726
57	13981
58	14109
59	14031
60	14251
61	14535
62	15059
63	15597
64	15969
65	15835
66	15893
67	15772
68	15754
69	15946
70	16171
71	17038
72	17653
73	18072
74	18695
75	19466
76	20027
77	19903
78	19575
79	20583
80	21552
81	23077
82	24570
83	25664
84	26763
85	27768
86	29415
87	31293
88	32996
89	35489
90	38599
91	41116
92	44095
93	46013
94	48206
95	49586
96	51135
97	52347
98	53542
99	53615
100	53501
101	51680
102	50974
103	49055
104	46364
105	42750
106	38356
107	34326
108	31154
109	28871
110	27322
111	25394
112	24364
113	23327
114	22162
115	21469
116	20995
117	20541
118	19500
119	18696
120	18068
121	17923
122	17670
123	16700
124	15707
125	15292
126	15150
127	15407
128	15664
129	15368
130	14827
131	14384
132	14106
133	14126
134	13542
135	13520
136	13432
137	13408
138	13633
139	13339
140	13906
141	14257
142	15013
143	14766
144	14132
145	13869
146	13422
147	13069
148	13330
149	13467
150	13587
151	13745
152	13610
153	13375
154	13854
155	14016
156	14047
157	14270
158	13865
159	13628
160	13640
161	13494
162	13770
163	13531
164	13632
165	13291
166	13834
167	13530
168	13298
169	13302
170	12891
171	12683
172	12602
173	12646
174	13043
175	13137
176	13250
177	13235
178	13539
179	13232
180	13351
181	12983
182	13025
183	12605
184	12722
185	13197
186	13224
187	13087
188	12748
189	13004
190	13307
191	13633
192	13766
193	13750
194	12853
195	12637
196	12446
197	12636
198	12732
199	13187
200	13177
201	13176
202	13100
203	12912
204	12774
205	13510
206	14104
207	15098
208	15922
209	16121
210	15731
211	15420
212	15958
213	16012
214	16588
215	16699
216	16572
217	16790
218	17601
219	19296
220	20001
221	20368
222	20822
223	21658
224	22156
225	22818
226	23775
227	25421
228	26747
229	27506
230	28460
231	29471
232	30470
233	31318
234	31347
235	31754
236	31974
237	32092
238	32575
239	31559
240	31060
241	29518
242	28008
243	26734
244	25595
245	23493
246	22377
247	20722
248	19339
249	17982
250	17301
251	16870
252	16866
253	17141
254	17039
255	16546
256	15989
257	16037
258	15951
259	16325
260	16747
261	17177
262	17175
263	17130
264	16989
265	17034
266	16702
267	15837
268	15798
269	15525
270	15464
271	15815
272	16205
273	16653
274	16597
275	16930
276	16619
277	15970
278	15415
279	14923
280	14598
281	13969
282	13816
283	14126
284	14195
285	13660
286	12918
287	13160
288	13268
289	13951
290	13928
291	13957
292	13406
293	13445
294	13379
295	14064
296	14148
297	14432
298	14716
299	15263
300	16198
301	16779
302	17625
303	18074
304	17800
305	17280
306	17193
307	17031
308	15894
309	15134
310	15252
311	15106
312	15211
313	14951
314	14505
315	14141
316	14239
317	14085
318	13842
319	13525
320	13400
321	13736
322	14685
323	14744
324	15058
325	15907
326	16526
327	16896
328	16668
329	17041
330	17635
331	18090
332	17672
333	17430
334	17293
335	17692
336	18377
337	18793
338	19432
339	20228
340	20610
341	20399
342	20198
343	19233
344	18920
345	18408
346	18054
347	17140
348	16580
349	16020
350	16056
351	16643
352	17177
353	17445
354	17299
355	16997
356	16974
357	16950
358	16606
359	16064
360	16256
361	16056
362	15793
363	15290
364	15292
365	15170
366	15121
367	14983
368	14842
369	14765
370	14783
371	14845
372	14284
373	14117
374	14611
375	14150
376	13733
377	12777
378	12632
379	12897
380	13920
381	14412
382	14561
383	14488
384	14303
385	14264
386	14151
387	14100
388	14324
389	14264
390	13651
391	13115
392	12978
393	12830
394	12864
395	12704
396	13081
397	13564
398	14215
399	14611
400	14411
401	14385
402	14064
403	14465
404	14408
405	13960
406	13825
407	13804
408	14431
409	14045
410	13779
411	13243
412	13218
413	13442
414	13636
415	14446
416	14331
417	13940
418	13823
419	14047
420	14331
421	13704
422	13456
423	13553
424	13381
425	12882
426	12767
427	13409
428	14017
429	14729
430	14965
431	14480
432	13894
433	13635
434	13581
435	13303
436	12932
437	12448
438	12331
439	12706
440	13507
441	13404
442	13265
443	12993
444	12730
445	12772
446	13052
447	13174
448	13661
449	13458
450	13102
451	12213
452	12345
453	12743
454	13257
455	13213
456	12993
457	12797
458	12165
459	12242
460	13040
461	13560
462	13465
463	13850
464	14782
465	15515
466	15800
467	15587
468	15853
469	16787
470	16729
471	16438
472	16635
473	17278
474	18170
475	18848
476	18944
477	18727
478	18128
479	17645
480	17694
481	17868
482	17920
483	18193
484	18240
485	17566
486	16648
487	15910
488	15682
489	16191
490	16055
491	15305
492	15315
493	15938
494	15356
495	14482
496	14014
497	13799
498	14158
499	14502
500	14507
501	14364
502	14054
503	14139
504	14218
505	14218
506	14310
507	14162
508	14213
509	14544
510	14785
511	14174
512	14481
513	15614
514	16371
515	16591
516	16373
517	15825
518	14948
519	14416
520	13642
521	13376
522	14043
523	15156
524	16236
525	16025
526	15701
527	15736
528	15550
529	15219
530	15245
531	14959
532	14937
533	14909
534	14519
535	14358
536	14748
537	15935
538	16896
539	16108
540	15141
541	14762
542	15558
543	15467
544	15342
545	15381
546	15229
547	15700
548	15657
549	14919
550	14314
551	14496
552	14978
553	15798
554	16558
555	17022
556	16892
557	16462
558	17251
559	18601
560	18642
561	17672
562	17157
563	16730
564	17015
565	17427
566	17384
567	17297
568	17064
569	16974
570	17048
571	17004
572	17653
573	19207
574	19719
575	19621
576	20143
577	19912
578	19126
579	19519
580	19795
581	19610
582	18694
583	18898
584	20269
585	21486
586	21543
587	21648
588	21815
589	20971
590	19957
591	19316
592	19312
593	20044
594	21137
595	21662
596	22182
597	22323
598	22297
599	21281
600	20686
601	21505
602	22554
603	23271
604	23033
605	23069
606	23108
607	22874
608	22120
609	22188
610	23784
611	24667
612	25056
613	26358
614	25580
615	24239
616	24621
617	26288
618	26558
619	26238
620	26679
621	27998
622	29258
623	29112
624	28029
625	28332
626	28498
627	27460
628	26901
629	27515
630	29104
631	30223
632	30353
633	30447
634	31435
635	32920
636	33257
637	31182
638	31025
639	31925
640	33538
641	35535
642	35594
643	35799
644	35653
645	35449
646	36274
647	37328
648	38281
649	39055
650	40086
651	41559
652	43684
653	46106
654	45652
655	44507
656	45024
657	46861
658	48931
659	49907
660	49817
661	49688
662	50737
663	51429
664	52200
665	53519
666	56484
667	57555
668	58352
669	61108
670	63868
671	67745
672	69111
673	70663
674	73328
675	73653
676	75464
677	76505
678	77387
679	78995
680	81021
681	83791
682	87477
683	91207
684	93046
685	96450
686	97136
687	96555
688	101172
689	104374
690	109321
691	112598
692	113214
693	111586
694	110487
695	112610
696	114122
697	114380
698	115902
699	118175
700	118669
701	120510
702	124460
703	127648
704	129455
705	129774
706	129321
707	129038
708	129369
709	133260
710	134483
711	133387
712	130479
713	129725
714	130460
715	131887
716	132672
717	134011
718	132621
719	133944
720	136898
721	136869
722	132834
723	128297
724	130240
725	130445
726	128204
727	125594
728	125610
729	124754
730	124485
731	120953
732	115343
733	112247
734	107452
735	102294
736	98455
737	98432
738	95394
739	91951
740	87237
741	83173
742	83409
743	80725
744	80682
745	80646
746	77788
747	74376
748	73497
749	70471
750	68452
751	66332
752	63836
753	65532
754	66280
755	65079
756	61541
757	60023
758	61039
759	61561
760	59308
761	59694
762	59695
763	57336
764	56877
765	58988
766	59494
767	60565
768	59348
769	57690
770	56404
771	55951
772	54432
773	52158
774	50546
775	50644
776	51344
777	50571
778	48680
779	48187
780	50316
781	51409
782	51779
783	51731
784	50991
785	49235
786	47994
787	48119
788	47859
789	47607
790	48501
791	50112
792	47362
793	46343
794	48047
795	48510
796	46986
797	46608
798	47540
799	47492
800	47119
801	48507
802	50645
803	50169
804	46875
805	44605
806	44784
807	46422
808	47181
809	46987
810	46930
811	48730
812	49593
813	49417
814	47537
815	49045
816	49165
817	47290
818	46695
819	48079
820	49326
821	51373
822	52259
823	50929
824	50125
825	50203
826	49648
827	48471
828	47595
829	47744
830	46360
831	42782
832	41575
833	43370
834	46489
835	46424
836	45521
837	42868
838	40030
839	40232
840	40004
841	39710
842	40694
843	40039
844	37970
845	37346
846	38915
847	39181
848	36260
849	34714
850	32881
851	33390
852	33698
853	32463
854	31135
855	30208
856	29221
857	28990
858	29429
859	29428
860	28420
861	27774
862	26212
863	26421
864	27527
865	27561
866	26820
867	26571
868	26767
869	26657
870	26357
871	26907
872	26314
873	27238
874	26803
875	25818
876	26802
877	25942
878	24231
879	22564
880	22091
881	23499
882	24362
883	24049
884	23033
885	22278
886	21998
887	23822
888	23855
889	23326
890	25029
891	23901
892	22288
893	21148
894	20446
895	20575
896	21499
897	21847
898	22611
899	23665
900	23756
901	22873
902	20346
903	19199
904	19362
905	20316
906	20468
907	19071
908	18278
909	18776
910	20386
911	21199
912	21334
913	20628
914	21026
915	20267
916	20378
917	19006
918	19720
919	19890
920	18876
921	18200
922	19397
923	19150
924	19556
925	19180
926	18518
927	17995
928	19650
929	19787
930	19848
931	19595
932	19720
933	19033
934	17878
935	18644
936	19561
937	19455
938	19504
939	18616
940	18869
941	19000
942	17837
943	17810
944	18797
945	18438
946	18725
947	19124
948	19331
949	19868
950	20713
951	21616
952	21142
953	21055
954	21633
955	20827
956	20824
957	20608
958	20740
959	23828
960	23703
961	21104
962	19115
963	20142
964	20440
965	18371
966	19196
967	19604
968	19304
969	18536
970	17981
971	19868
972	21022
973	20801
974	20402
975	19726
976	19699
977	18786
978	18022
979	18056
980	18731
981	19335
982	19066
983	18870
984	18099
985	16759
986	16661
987	17346
988	17482
989	19167
990	19465
991	18927
992	19308
993	19550
994	16590
995	16686
996	17982
997	17162
998	16489
999	16432
1000	15347
1001	15715
1002	17036
1003	16580
1004	14989
1005	14963
1006	15251
1007	14677
1008	14182
1009	14251
1010	15018
1011	14196
1012	14076
1013	15339
1014	15561
1015	16150
1016	17521
1017	17457
1018	15385
1019	13803
1020	14578
1021	14914
1022	14778
1023	14774
1024	14221