1	11909
2	12013
3	12002
4	11952
5	11695
6	11513
7	11709
8	11659
9	11990
10	11868
11	11972
12	11897
13	11652
14	11890
15	12079
16	12205
17	12554
18	12736
19	12929
20	12966
21	12613
22	12837
23	13223
24	13670
25	14059
26	14063
27	13751
28	13617
29	13044
30	13255
31	13171
32	13227
33	13212
34	13281
35	13577
36	13935
37	14004
38	13591
39	13464
40	13358
41	13440
42	13296
43	13172
44	13282
45	13650
46	13914
47	14113
48	14370
49	14222
50	13905
51	14011
52	13673
53	14303
54	14572
55	14656
56	14592
57	14603
58	14912
59	14979
60	15226
61	14918
62	14340
63	14360
64	14088
65	14321
66	14690
67	15105
68	15555
69	15977
70	16536
71	17124
72	17617
73	18050
74	18646
75	19249
76	19608
77	19701
78	19467
79	19568
80	19457
81	19414
82	19302
83	18789
84	18431
85	18784
86	18928
87	19333
88	19743
89	20232
90	21281
91	22105
92	22881
93	23446
94	22884
95	22412
96	22551
97	23580
98	24885
99	26183
100	27359
101	27904
102	28666
103	29176
104	29926
105	30604
106	31110
107	31826
108	32256
109	32407
110	33208
111	34209
112	35326
113	36089
114	36900
115	37497
116	37793
117	38305
118	37993
119	37089
120	37062
121	38538
122	39338
123	40327
124	41038
125	42067
126	42054
127	40967
128	39093
129	37748
130	37238
131	37093
132	37136
133	36706
134	35782
135	34423
136	33175
137	32648
138	32141
139	30860
140	30447
141	29048
142	28244
143	27703
144	27372
145	27377
146	27097
147	26177
148	25803
149	24919
150	24292
151	24192
152	24365
153	24075
154	23752
155	23292
156	22699
157	21883
158	21125
159	20286
160	20057
161	19363
162	19437
163	19109
164	19253
165	19556
166	19544
167	19406
168	18840
169	18705
170	18199
171	17862
172	17634
173	17720
174	17518
175	17117
176	16600
177	16529
178	17035
179	17909
180	18011
181	17341
182	16710
183	16432
184	15829
185	15504
186	15265
187	15278
188	15782
189	16018
190	16142
191	16138
192	15513
193	14804
194	14236
195	14780
196	15302
197	15870
198	15573
199	15211
200	14921
201	15136
202	15185
203	15152
204	14909
205	14650
206	14278
207	14529
208	14958
209	14997
210	15306
211	15583
212	15947
213	15730
214	15972
215	16085
216	16338
217	16214
218	15838
219	15735
220	15665
221	16090
222	15909
223	15244
224	15004
225	14934
226	15223
227	15536
228	15688
229	15611
230	15767
231	15423
232	15456
233	15442
234	15406
235	15670
236	16009
237	16134
238	15839
239	15298
240	15252
241	14887
242	14820
243	14766
244	14824
245	14986
246	15437
247	15383
248	15560
249	15378
250	15514
251	15717
252	15766
253	15634
254	15304
255	15141
256	15177
257	15551
258	15771
259	16526
260	16784
261	16843
262	17191
263	17005
264	17069
265	16643
266	16300
267	15795
268	16189
269	16866
270	16846
271	17195
272	17431
273	17731
274	17477
275	17491
276	17336
277	17434
278	17974
279	18293
280	18806
281	19095
282	19595
283	19320
284	18768
285	18361
286	17895
287	18163
288	17956
289	18752
290	19652
291	20660
292	21104
293	21312
294	21661
295	21427
296	21046
297	20741
298	21310
299	21854
300	21890
301	21788
302	21889
303	22406
304	22267
305	21984
306	21894
307	22543
308	22573
309	23190
310	23923
311	23993
312	23958
313	24299
314	24599
315	25296
316	25306
317	26233
318	25523
319	25598
320	26259
321	27355
322	28435
323	28903
324	28625
325	28144
326	27069
327	27102
328	27869
329	28729
330	28870
331	28261
332	27463
333	26944
334	27227
335	28812
336	30552
337	31279
338	31299
339	30707
340	29623
341	29075
342	29144
343	29570
344	30447
345	31106
346	31503
347	31228
348	30549
349	29455
350	28770
351	28564
352	29484
353	30041
354	30365
355	30175
356	30643
357	30919
358	31064
359	30294
360	29691
361	29304
362	29037
363	28177
364	28110
365	28142
366	28365
367	28048
368	27822
369	28012
370	28147
371	28317
372	28322
373	28431
374	27979
375	27825
376	27771
377	27834
378	27568
379	28050
380	28983
381	29294
382	29087
383	29015
384	29157
385	29759
386	29620
387	29402
388	30471
389	31056
390	30204
391	29377
392	29443
393	29764
394	29856
395	30274
396	31828
397	33095
398	33847
399	33346
400	32854
401	32742
402	33066
403	32792
404	32835
405	33051
406	34012
407	34777
408	36614
409	37701
410	39348
411	39404
412	39076
413	38829
414	38878
415	38729
416	38644
417	38888
418	39129
419	39984
420	41546
421	44548
422	45752
423	45328
424	43474
425	42686
426	42734
427	42920
428	43453
429	44507
430	45745
431	46229
432	45849
433	46149
434	46510
435	46367
436	45085
437	45020
438	45786
439	46013
440	45984
441	45592
442	46609
443	48280
444	50006
445	51079
446	53847
447	54715
448	56295
449	56512
450	55541
451	54180
452	54308
453	54616
454	55794
455	57416
456	59372
457	60645
458	61762
459	64277
460	65373
461	66609
462	68194
463	70349
464	71701
465	72212
466	73891
467	75436
468	77151
469	79976
470	80024
471	80914
472	81341
473	84440
474	86378
475	88337
476	91162
477	94261
478	96490
479	97386
480	98214
481	99785
482	101431
483	102301
484	102525
485	102229
486	104673
487	107848
488	109186
489	111057
490	112250
491	112374
492	110834
493	113604
494	114127
495	115404
496	116714
497	118599
498	120287
499	119569
500	119666
501	120884
502	122752
503	124369
504	126730
505	129299
506	134017
507	136849
508	140544
509	144405
510	148010
511	149702
512	150712
513	153474
514	152504
515	154457
516	158833
517	162617
518	167002
519	169605
520	172481
521	173964
522	178056
523	179975
524	182807
525	186426
526	187770
527	191717
528	195121
529	198817
530	200384
531	202547
532	205530
533	210705
534	214138
535	217425
536	219927
537	221114
538	223017
539	223319
540	225370
541	230526
542	233845
543	233169
544	233425
545	235256
546	233647
547	227756
548	221354
549	218277
550	224374
551	230350
552	231052
553	228968
554	225586
555	222176
556	224252
557	230428
558	229059
559	223987
560	221890
561	216794
562	218350
563	221802
564	226745
565	228975
566	231566
567	233498
568	235897
569	236594
570	238303
571	238647
572	236608
573	228862
574	222608
575	228081
576	232605
577	234634
578	234629
579	234349
580	235906
581	234365
582	230643
583	224282
584	218157
585	215803
586	213924
587	212243
588	203906
589	195443
590	189667
591	192120
592	189685
593	182513
594	175216
595	170310
596	166971
597	160353
598	155918
599	151873
600	146666
601	142997
602	139295
603	135313
604	131126
605	126938
606	124076
607	124273
608	122739
609	118148
610	113880
611	112075
612	111074
613	109708
614	106615
615	103069
616	99882
617	99665
618	97098
619	92421
620	90046
621	92577
622	94420
623	92938
624	89074
625	86176
626	85818
627	85382
628	85859
629	83512
630	82232
631	80709
632	78855
633	79434
634	80028
635	79899
636	79908
637	79992
638	76421
639	74251
640	74134
641	75241
642	75000
643	76628
644	77899
645	78405
646	75854
647	72664
648	71992
649	72189
650	73710
651	74474
652	74082
653	71360
654	68369
655	69166
656	68509
657	67063
658	66972
659	66906
660	65820
661	63344
662	62803
663	62385
664	61370
665	59217
666	56680
667	56667
668	58590
669	60708
670	59320
671	57783
672	56710
673	54208
674	52887
675	52148
676	52080
677	51189
678	50531
679	51035
680	51730
681	50692
682	49413
683	50445
684	49549
685	46732
686	45736
687	45397
688	44857
689	45703
690	46278
691	45618
692	44827
693	43401
694	41985
695	42465
696	43826
697	42980
698	40433
699	37536
700	37359
701	38476
702	39424
703	40240
704	37994
705	37097
706	38130
707	37425
708	35869
709	36104
710	37751
711	37173
712	36676
713	36108
714	35638
715	36308
716	35946
717	34811
718	34662
719	34926
720	36162
721	35481
722	34198
723	34163
724	34613
725	33450
726	33237
727	33165
728	33004
729	32254
730	32393
731	32079
732	31011
733	31680
734	30635
735	29975
736	30043
737	30698
738	30538
739	28469
740	27712
741	28236
742	30308
743	29634
744	28390
745	28321
746	28239
747	27953
748	28385
749	28720
750	27458
751	25160
752	23849
753	22963
754	22726
755	23530
756	23976
757	24279
758	23415
759	22653
760	21637
761	22715
762	21892
763	20742
764	19771
765	19727
766	20363
767	20308
768	19764
769	19071
770	18209
771	18716
772	19668
773	19237
774	18548
775	18579
776	18701
777	19770
778	19348
779	19530
780	20409
781	20448
782	20024
783	18895
784	17833
785	17480
786	18707
787	19893
788	19958
789	19048
790	17889
791	17704
792	17876
793	17436
794	17684
795	18544
796	17936
797	17211
798	17220
799	17721
800	17046
801	16241
802	16001
803	16570
804	16521
805	16378
806	16358
807	15573
808	15510
809	16581
810	16722
811	15441
812	15771
813	16200
814	16960
815	17342
816	17100
817	15981
818	15692
819	15059
820	15588
821	16600
822	15619
823	15443
824	16033
825	15815
826	15267
827	15468
828	15461
829	14912
830	14318
831	14388
832	14957
833	15832
834	16548
835	16057
836	15444
837	15951
838	16666
839	16140
840	16093
841	14921
842	13777
843	15391
844	16281
845	15057
846	14679
847	14217
848	13629
849	13571
850	14195
851	15112
852	14578
853	14255
854	14206
855	13989
856	14847
857	14649
858	14620
859	15961
860	16387
861	15769
862	14826
863	14317
864	14701
865	15724
866	15757
867	14187
868	14185
869	15543
870	15404
871	13863
872	13344
873	13981
874	14352
875	14251
876	14122
877	13887
878	14141
879	13789
880	13349
881	13060
882	13302
883	13625
884	13734
885	13381
886	13291
887	12052
888	12312
889	12709
890	12984
891	13056
892	13438
893	13310
894	12274
895	12785
896	12841
897	13037
898	13711
899	13297
900	13353
901	13645
902	12826
903	12701
904	13407
905	13198
906	13384
907	11960
908	11624
909	11952
910	11812
911	12275
912	13476
913	13010
914	13131
915	12803
916	13245
917	12927
918	12123
919	12294
920	12756
921	13238
922	13101
923	13083
924	13083
925	13403
926	13205
927	12487
928	12599
929	12866
930	13390
931	12774
932	13065
933	13374
934	14163
935	14845
936	14379
937	13550
938	13489
939	12980
940	12861
941	13409
942	13674
943	12841
944	13132
945	12675
946	12153
947	12207
948	12492
949	13130
950	12622
951	12601
952	12584
953	12794
954	12862
955	13008
956	13871
957	13731
958	13575
959	13069
960	12676
961	13336
962	13749
963	13307
964	13400
965	13294
966	13427
967	13299
968	11615
969	11086
970	12027
971	12356
972	11450
973	11297
974	11394
975	11922
976	12960
977	12859
978	13104
979	12409
980	12572
981	12592
982	12638
983	13376
984	13436
985	12796
986	12716
987	14404
988	13716
989	12909
990	11795
991	11311
992	11313
993	12502
994	12745
995	12382
996	11730
997	11852
998	12566
999	13317
1000	12577
1001	12262
1002	13087
1003	12938
1004	12331
1005	12582
1006	13616
1007	13209
1008	12412
1009	11969
1010	11256
1011	11476
1012	12323
1013	12552
1014	12067
1015	11884
1016	11901
1017	12065
1018	13021
1019	13529
1020	12827
1021	11781
1022	12455
1023	13257
1024	13516