1	17894
2	18071
3	18508
4	19263
5	19460
6	19713
7	20705
8	21993
9	22034
10	21660
11	21856
12	22205
13	22434
14	22192
15	21474
16	21319
17	21554
18	22070
19	23802
20	24920
21	25538
22	25947
23	24527
24	22675
25	21410
26	21671
27	22822
28	23792
29	24045
30	24622
31	25455
32	24485
33	24334
34	23580
35	24049
36	23828
37	23524
38	23148
39	22290
40	21707
41	22138
42	22866
43	23091
44	23821
45	25097
46	24667
47	23867
48	22962
49	21507
50	20855
51	20934
52	21462
53	22689
54	23184
55	22639
56	22299
57	21126
58	19942
59	19755
60	20984
61	22055
62	24034
63	24193
64	23921
65	23471
66	23370
67	22916
68	22791
69	22762
70	22581
71	22769
72	23053
73	22488
74	21963
75	21807
76	20947
77	20458
78	19807
79	21627
80	22961
81	25410
82	26266
83	26236
84	25644
85	25669
86	25103
87	25070
88	25132
89	24731
90	25151
91	25425
92	25299
93	25560
94	25672
95	24885
96	23771
97	21883
98	19979
99	20030
100	20413
101	20239
102	19177
103	18676
104	18322
105	16854
106	16903
107	17031
108	17370
109	17658
110	19421
111	20725
112	22744
113	24016
114	24618
115	24686
116	25316
117	26414
118	27267
119	26882
120	26524
121	26113
122	25556
123	25388
124	25074
125	25043
126	25455
127	26164
128	27130
129	27357
130	26589
131	25279
132	24236
133	23733
134	24074
135	23262
136	22922
137	23812
138	24669
139	25240
140	25133
141	23586
142	22295
143	21149
144	21473
145	21951
146	22095
147	23289
148	23865
149	24393
150	24423
151	25238
152	24305
153	23536
154	22473
155	22037
156	21845
157	21428
158	21599
159	21756
160	21918
161	21454
162	21285
163	21962
164	22809
165	23327
166	23768
167	24073
168	25064
169	25725
170	25815
171	26043
172	26252
173	25766
174	25163
175	25539
176	26110
177	25764
178	25047
179	24323
180	23994
181	23394
182	23272
183	23769
184	24741
185	25304
186	26174
187	26857
188	28386
189	28515
190	27678
191	26639
192	23529
193	21917
194	20836
195	20570
196	21939
197	22716
198	23186
199	23134
200	22373
201	22262
202	22286
203	23480
204	24637
205	24942
206	24643
207	25100
208	24665
209	24422
210	23863
211	24153
212	25012
213	23857
214	23237
215	24009
216	23952
217	25374
218	26819
219	28972
220	29624
221	28899
222	27156
223	27652
224	26898
225	27080
226	26322
227	26719
228	25585
229	23812
230	23812
231	26018
232	27144
233	26618
234	25180
235	24773
236	25128
237	25396
238	24028
239	23057
240	23056
241	24004
242	24853
243	24970
244	25153
245	25024
246	25062
247	26477
248	27592
249	27957
250	26510
251	25391
252	24941
253	24941
254	24300
255	23347
256	23671
257	24274
258	24888
259	26374
260	27994
261	29937
262	29836
263	28661
264	26843
265	25405
266	24891
267	26019
268	28197
269	30427
270	29792
271	29460
272	29637
273	29607
274	29983
275	31101
276	32748
277	34528
278	34221
279	32845
280	30303
281	29683
282	31450
283	31985
284	32273
285	31938
286	30919
287	30154
288	28529
289	28624
290	30077
291	30884
292	29398
293	28036
294	28593
295	29451
296	28897
297	28501
298	28336
299	29282
300	30273
301	31524
302	30880
303	29533
304	28988
305	29258
306	28099
307	26175
308	25512
309	24555
310	25255
311	26448
312	28495
313	30384
314	29779
315	27843
316	26331
317	27071
318	26894
319	27290
320	28520
321	29934
322	29900
323	29068
324	28575
325	28347
326	27485
327	28659
328	30103
329	32768
330	31734
331	29717
332	29467
333	30549
334	32893
335	33918
336	33792
337	34040
338	33655
339	32256
340	31092
341	30783
342	29644
343	29119
344	30107
345	32323
346	34074
347	35431
348	34150
349	33751
350	33250
351	32402
352	31491
353	30753
354	30917
355	30888
356	32271
357	32790
358	32254
359	31578
360	32028
361	32119
362	31315
363	30532
364	31059
365	31031
366	31377
367	31388
368	32057
369	31995
370	32462
371	34253
372	37399
373	40155
374	39476
375	38405
376	38959
377	39315
378	39177
379	38739
380	38852
381	39910
382	41155
383	38834
384	36786
385	35954
386	36559
387	37406
388	37338
389	36599
390	35822
391	36753
392	35625
393	35274
394	35302
395	36039
396	35083
397	33711
398	35671
399	39385
400	41078
401	42178
402	42799
403	44095
404	46050
405	48451
406	48450
407	43903
408	41320
409	42287
410	46535
411	48474
412	47442
413	45643
414	44836
415	45234
416	44276
417	44809
418	44188
419	42825
420	44260
421	45023
422	43776
423	40645
424	38293
425	36692
426	38191
427	41763
428	45427
429	45951
430	45664
431	46756
432	48494
433	49318
434	49351
435	49290
436	49305
437	50499
438	50384
439	47987
440	45478
441	43896
442	44078
443	47581
444	53889
445	55868
446	56162
447	54161
448	51574
449	48559
450	49239
451	51848
452	53490
453	53203
454	52580
455	50869
456	50611
457	52366
458	55801
459	56396
460	53581
461	53198
462	54295
463	56559
464	58990
465	62133
466	64392
467	64295
468	62214
469	62126
470	58955
471	57285
472	58507
473	59058
474	58441
475	57839
476	57825
477	60215
478	65145
479	66504
480	61970
481	58089
482	57773
483	61705
484	65306
485	65434
486	67486
487	70371
488	74979
489	77706
490	77961
491	75241
492	74342
493	79256
494	80894
495	79650
496	78415
497	76312
498	76030
499	76029
500	78787
501	80902
502	80939
503	81865
504	81277
505	83044
506	85950
507	86205
508	82301
509	78146
510	78690
511	80871
512	84524
513	88810
514	91064
515	93689
516	95774
517	98944
518	102047
519	102469
520	101000
521	98665
522	102682
523	109467
524	114314
525	112017
526	108427
527	109321
528	108697
529	107164
530	107979
531	112638
532	113209
533	115707
534	118218
535	127386
536	133151
537	131925
538	129402
539	131472
540	137915
541	142607
542	140515
543	142264
544	145441
545	153110
546	156015
547	154082
548	149941
549	149319
550	152681
551	159160
552	165476
553	169894
554	170764
555	169813
556	167828
557	171617
558	180402
559	188879
560	192846
561	196432
562	198254
563	199669
564	208267
565	212234
566	219281
567	230096
568	243182
569	253063
570	260111
571	269675
572	276288
573	274982
574	272724
575	284482
576	291841
577	291451
578	292396
579	299867
580	316646
581	329201
582	336915
583	347621
584	355564
585	357659
586	360740
587	374117
588	387989
589	404611
590	412876
591	424159
592	435908
593	441623
594	455589
595	479796
596	491876
597	489815
598	503414
599	522604
600	536982
601	559312
602	578122
603	598216
604	620168
605	641469
606	662541
607	674114
608	669324
609	696812
610	730031
611	749945
612	773749
613	793562
614	797672
615	803743
616	819342
617	864608
618	877090
619	868953
620	870648
621	894247
622	922297
623	934050
624	935780
625	928532
626	930969
627	939391
628	968527
629	978313
630	1001221
631	1017890
632	1021196
633	1021812
634	994325
635	973504
636	975402
637	977429
638	970969
639	972868
640	982035
641	992775
642	964573
643	959058
644	964422
645	971132
646	971086
647	955468
648	941797
649	917525
650	920669
651	917928
652	915203
653	921871
654	922182
655	916595
656	908958
657	917410
658	911622
659	871409
660	837645
661	806771
662	765822
663	724182
664	699173
665	690811
666	682439
667	650500
668	611353
669	573348
670	543076
671	539979
672	536155
673	515878
674	498023
675	471605
676	441642
677	419644
678	409351
679	394950
680	386179
681	382007
682	377781
683	363245
684	351890
685	354714
686	342004
687	327821
688	309475
689	296239
690	295669
691	292380
692	282217
693	270830
694	258194
695	256477
696	255239
697	233839
698	215404
699	213941
700	217609
701	217337
702	219189
703	224139
704	221835
705	208502
706	196140
707	189131
708	185361
709	182429
710	178735
711	177669
712	178404
713	176804
714	170087
715	164667
716	164029
717	159539
718	157479
719	157047
720	150639
721	141580
722	141428
723	134740
724	132705
725	133748
726	135146
727	137339
728	139367
729	128039
730	121831
731	119419
732	116147
733	116499
734	117005
735	120922
736	121563
737	116499
738	114378
739	114701
740	109751
741	105511
742	110557
743	109586
744	102794
745	96462
746	95270
747	95564
748	99509
749	99000
750	94584
751	93306
752	95405
753	93458
754	90359
755	91046
756	91302
757	89209
758	83514
759	84019
760	83376
761	83662
762	81231
763	80861
764	79083
765	84045
766	88026
767	85016
768	82476
769	76532
770	75484
771	80104
772	85355
773	84025
774	81391
775	75599
776	68828
777	64049
778	63238
779	66320
780	71293
781	73192
782	66525
783	61745
784	63934
785	66552
786	69543
787	71516
788	65824
789	62557
790	60545
791	61559
792	61398
793	60895
794	59890
795	58550
796	59884
797	58850
798	59855
799	58549
800	51714
801	52750
802	57476
803	56082
804	52553
805	53157
806	53741
807	52795
808	49149
809	44202
810	42038
811	39416
812	40385
813	42849
814	45964
815	48252
816	51170
817	46828
818	39991
819	42700
820	43225
821	42465
822	41909
823	43127
824	49403
825	51116
826	48178
827	47672
828	45304
829	42126
830	40500
831	43236
832	44570
833	41861
834	41400
835	39893
836	38964
837	40314
838	37980
839	37073
840	38241
841	35764
842	34215
843	32354
844	33137
845	34619
846	38088
847	43324
848	45752
849	41215
850	38447
851	39399
852	34409
853	34068
854	34607
855	32377
856	37623
857	41907
858	41713
859	38791
860	36512
861	36807
862	37215
863	36492
864	33778
865	32841
866	34402
867	35953
868	35964
869	36032
870	34121
871	35211
872	37772
873	39993
874	36167
875	34858
876	32520
877	31587
878	33406
879	33171
880	30310
881	30065
882	29740
883	27829
884	30096
885	33917
886	33047
887	32126
888	28857
889	27693
890	28102
891	28506
892	31824
893	32186
894	30362
895	30153
896	31656
897	30706
898	29390
899	31423
900	30830
901	30389
902	35266
903	39783
904	32462
905	29975
906	30341
907	31781
908	29743
909	31434
910	32459
911	32831
912	34642
913	31466
914	32159
915	30519
916	28273
917	29432
918	31226
919	28831
920	27333
921	26931
922	29500
923	29543
924	29850
925	29957
926	24973
927	24335
928	28347
929	27339
930	26307
931	26341
932	25940
933	24941
934	23946
935	23087
936	24913
937	26230
938	25035
939	26415
940	27211
941	26181
942	26728
943	24895
944	25533
945	28872
946	29934
947	28864
948	26770
949	23241
950	21266
951	21968
952	23360
953	23528
954	24105
955	24202
956	24679
957	23751
958	22792
959	23755
960	23529
961	25708
962	23212
963	23158
964	25104
965	24151
966	25473
967	24835
968	26762
969	27923
970	28708
971	26668
972	23715
973	25848
974	25124
975	23019
976	25832
977	29894
978	28858
979	25541
980	23054
981	20905
982	19871
983	21895
984	23732
985	22654
986	21784
987	21751
988	20828
989	23245
990	26821
991	26058
992	23422
993	23129
994	19204
995	18483
996	19422
997	21922
998	24391
999	21861
1000	23478
1001	23226
1002	22877
1003	24717
1004	21929
1005	19906
1006	21276
1007	22706
1008	22473
1009	21480
1010	23458
1011	25722
1012	28521
1013	27333
1014	22500
1015	22830
1016	21026
1017	20529
1018	21614
1019	22136
1020	20670
1021	19563
1022	19960
1023	18245
1024	17416