1	20038
2	19737
3	20058
4	19605
5	19398
6	19196
7	19491
8	19479
9	19804
10	19497
11	19323
12	19105
13	19226
14	19604
15	19762
16	19741
17	19026
18	18567
19	18130
20	18557
21	19157
22	19766
23	20602
24	20965
25	21214
26	21864
27	21904
28	21637
29	20615
30	19928
31	19242
32	19361
33	19403
34	19287
35	19472
36	19699
37	19865
38	19388
39	19525
40	19293
41	20015
42	20910
43	21439
44	21758
45	22660
46	21919
47	21688
48	21729
49	22020
50	22319
51	22259
52	21855
53	21776
54	21407
55	20916
56	21075
57	21568
58	21670
59	21799
60	22310
61	22869
62	22929
63	23569
64	23985
65	24428
66	24314
67	24336
68	24070
69	23353
70	23147
71	24087
72	24766
73	25271
74	25588
75	26129
76	26277
77	26759
78	27335
79	28072
80	29256
81	29989
82	30793
83	31328
84	31824
85	32162
86	34261
87	35787
88	36104
89	36468
90	36852
91	37476
92	38194
93	38813
94	38739
95	39112
96	38933
97	39373
98	39721
99	38962
100	38388
101	36931
102	36784
103	36760
104	36338
105	35968
106	34420
107	33064
108	31719
109	30533
110	30099
111	28790
112	28450
113	27288
114	26927
115	27309
116	27209
117	27042
118	26359
119	25775
120	25286
121	25502
122	25839
123	25682
124	25539
125	25538
126	25294
127	24924
128	23998
129	23717
130	23254
131	22864
132	22423
133	22033
134	21692
135	22133
136	21718
137	21818
138	21775
139	21774
140	22434
141	22054
142	22320
143	22409
144	22270
145	23007
146	22918
147	23385
148	24548
149	25278
150	25890
151	26501
152	26296
153	25661
154	25459
155	24602
156	24675
157	25016
158	25081
159	25294
160	24983
161	24596
162	24790
163	24218
164	24290
165	24051
166	24211
167	24078
168	23555
169	23415
170	23468
171	24387
172	24859
173	24888
174	24307
175	23285
176	23095
177	23890
178	24963
179	25290
180	24735
181	23825
182	24075
183	24010
184	23778
185	23735
186	24012
187	23651
188	23753
189	24108
190	24168
191	24045
192	24006
193	24920
194	25280
195	25957
196	24839
197	24044
198	23263
199	23106
200	23410
201	23934
202	24149
203	24217
204	23690
205	24105
206	23752
207	23925
208	24154
209	24219
210	24610
211	25088
212	25737
213	25382
214	25983
215	25893
216	26345
217	26771
218	27132
219	27702
220	28306
221	29565
222	30865
223	32120
224	32282
225	32293
226	32256
227	31970
228	32411
229	32660
230	33188
231	34285
232	35364
233	36425
234	36151
235	35781
236	35590
237	35615
238	35844
239	35237
240	35341
241	34740
242	34645
243	35027
244	35493
245	35265
246	35872
247	35684
248	35608
249	35228
250	35512
251	35416
252	36719
253	37632
254	38204
255	38392
256	37997
257	39288
258	40704
259	43037
260	45416
261	47104
262	48528
263	49218
264	50983
265	53645
266	56287
267	58043
268	61050
269	62884
270	62985
271	62458
272	61660
273	60877
274	59249
275	57999
276	55448
277	52582
278	49611
279	47076
280	45266
281	43546
282	42368
283	41029
284	39799
285	38382
286	37813
287	38499
288	38104
289	37810
290	37477
291	36350
292	35533
293	34525
294	35428
295	37352
296	40737
297	45252
298	50673
299	55514
300	59303
301	62340
302	64339
303	65274
304	63856
305	61108
306	57530
307	55192
308	52807
309	51629
310	51712
311	50221
312	49460
313	48951
314	49481
315	48709
316	48133
317	48030
318	48588
319	49549
320	51107
321	52580
322	54249
323	55638
324	57541
325	61235
326	63396
327	66998
328	69970
329	74386
330	79709
331	83725
332	86264
333	90561
334	95779
335	103834
336	111097
337	116952
338	121220
339	123424
340	124689
341	124546
342	122866
343	119516
344	119060
345	117175
346	113432
347	107810
348	102234
349	100942
350	100030
351	98796
352	96352
353	93893
354	92090
355	88667
356	85187
357	83305
358	82058
359	79927
360	78457
361	76288
362	72933
363	68346
364	65722
365	62755
366	60277
367	58336
368	55231
369	52338
370	49814
371	48255
372	47638
373	47096
374	46341
375	45471
376	44289
377	41913
378	39954
379	38554
380	38580
381	37905
382	36654
383	36465
384	37063
385	37861
386	37796
387	38044
388	38994
389	39674
390	38901
391	39017
392	38876
393	39932
394	41038
395	42129
396	41883
397	40974
398	41570
399	42458
400	42656
401	41731
402	40770
403	41251
404	41842
405	43141
406	43606
407	43087
408	43853
409	43157
410	42586
411	40769
412	40274
413	40807
414	40951
415	40748
416	40030
417	38803
418	38079
419	38584
420	39584
421	39763
422	39450
423	39450
424	39507
425	39740
426	40605
427	41668
428	40642
429	39660
430	40254
431	40927
432	40906
433	41224
434	41055
435	40098
436	38867
437	39810
438	39932
439	38188
440	37401
441	37575
442	38225
443	39152
444	39186
445	39225
446	39659
447	39874
448	41217
449	41756
450	41244
451	39708
452	40564
453	40731
454	42023
455	42764
456	43409
457	44120
458	45459
459	47778
460	50164
461	51868
462	53363
463	54652
464	55783
465	57571
466	62217
467	65729
468	69468
469	73505
470	75720
471	80031
472	81782
473	88712
474	94358
475	99171
476	100867
477	100369
478	99206
479	98985
480	98138
481	95112
482	91208
483	88476
484	87311
485	85392
486	83312
487	79422
488	73420
489	68016
490	62831
491	59482
492	56660
493	55383
494	53102
495	50634
496	49164
497	46513
498	44636
499	42114
500	40765
501	40699
502	40879
503	40072
504	39525
505	40387
506	41084
507	41364
508	41690
509	42002
510	42085
511	41106
512	41447
513	42427
514	42288
515	40652
516	40336
517	40184
518	39560
519	38214
520	37061
521	36079
522	36363
523	36166
524	34486
525	33415
526	33694
527	34221
528	34302
529	34375
530	35103
531	34983
532	34363
533	34392
534	33851
535	32912
536	32425
537	32857
538	33445
539	31947
540	31371
541	32168
542	33173
543	33408
544	33401
545	32811
546	31261
547	30907
548	31612
549	31182
550	31697
551	32795
552	32919
553	33359
554	34033
555	33515
556	33447
557	34103
558	34129
559	33111
560	32309
561	32511
562	34001
563	34162
564	34957
565	35350
566	35290
567	34911
568	34653
569	34678
570	36107
571	38192
572	38070
573	36272
574	35176
575	37019
576	37771
577	37477
578	37239
579	38521
580	39751
581	40113
582	40957
583	42140
584	42695
585	42996
586	43730
587	45262
588	46291
589	46942
590	47315
591	48825
592	49887
593	49503
594	49488
595	50376
596	52316
597	52342
598	52284
599	52408
600	52422
601	51893
602	51609
603	51955
604	50950
605	51984
606	54699
607	55893
608	53205
609	53547
610	57271
611	59023
612	58083
613	57982
614	56772
615	56419
616	56062
617	57282
618	58556
619	57790
620	56805
621	58107
622	59684
623	58519
624	57709
625	57853
626	57097
627	55905
628	55629
629	54108
630	53712
631	55992
632	57976
633	58312
634	56628
635	56379
636	58208
637	58172
638	55886
639	55224
640	57647
641	58157
642	57758
643	59136
644	60018
645	61759
646	63134
647	64142
648	66211
649	67242
650	68349
651	69709
652	69823
653	68192
654	67859
655	70696
656	72227
657	72614
658	71070
659	70527
660	70794
661	70915
662	72570
663	73774
664	76006
665	78807
666	79826
667	74829
668	72989
669	77673
670	81446
671	84162
672	84297
673	83240
674	82898
675	83168
676	84662
677	86640
678	87786
679	89595
680	89312
681	86688
682	85798
683	88287
684	88289
685	89832
686	93071
687	93865
688	93519
689	91995
690	93604
691	91215
692	90295
693	93234
694	93713
695	92008
696	90841
697	89642
698	90031
699	90892
700	89981
701	89408
702	90189
703	93109
704	95108
705	94507
706	95483
707	95174
708	93815
709	94322
710	95966
711	96465
712	96582
713	97336
714	95697
715	95701
716	95447
717	96287
718	95161
719	96129
720	98877
721	100072
722	98152
723	96370
724	96599
725	95837
726	96597
727	97605
728	97154
729	94591
730	94479
731	91136
732	87143
733	84730
734	80519
735	79449
736	80874
737	77873
738	73767
739	73686
740	74155
741	73179
742	74272
743	71127
744	70478
745	71971
746	69897
747	65325
748	64000
749	62998
750	61248
751	59249
752	58069
753	58726
754	61161
755	62968
756	61220
757	60302
758	58568
759	58806
760	57839
761	59792
762	60878
763	60295
764	57725
765	58418
766	58107
767	58324
768	56890
769	55034
770	53735
771	53646
772	55073
773	55264
774	55957
775	56479
776	54589
777	55050
778	55755
779	55129
780	54449
781	53605
782	52523
783	52812
784	52293
785	52526
786	53455
787	53514
788	52726
789	53198
790	51477
791	51923
792	52273
793	51582
794	51854
795	53503
796	51813
797	53399
798	53814
799	51487
800	48336
801	46948
802	48583
803	51193
804	49914
805	47768
806	48461
807	49616
808	50980
809	53358
810	52724
811	50284
812	49454
813	49427
814	50088
815	49511
816	46922
817	46223
818	45970
819	44629
820	43917
821	43906
822	42128
823	42590
824	45800
825	46708
826	47298
827	47759
828	47153
829	45817
830	44435
831	43940
832	43996
833	43490
834	43777
835	43225
836	44458
837	42313
838	39725
839	40080
840	41176
841	40476
842	39524
843	38958
844	39298
845	39737
846	40423
847	40644
848	41618
849	41652
850	38147
851	36123
852	37557
853	37688
854	36732
855	36348
856	34477
857	34278
858	35852
859	34241
860	33974
861	33403
862	32463
863	33186
864	32720
865	31650
866	31568
867	33443
868	34441
869	32470
870	31496
871	32334
872	32662
873	33608
874	32451
875	33221
876	33952
877	34691
878	34283
879	32197
880	31187
881	33008
882	33804
883	32265
884	30767
885	30040
886	31791
887	32102
888	31391
889	31912
890	32070
891	31775
892	30617
893	31220
894	31255
895	30382
896	29267
897	29637
898	30525
899	30438
900	28865
901	29092
902	30130
903	31458
904	32671
905	33723
906	33385
907	32721
908	33635
909	34512
910	36577
911	36714
912	37909
913	39344
914	38925
915	39391
916	40974
917	40279
918	37910
919	36450
920	35177
921	34925
922	35146
923	32124
924	30479
925	33035
926	33587
927	32142
928	30808
929	30014
930	32573
931	32593
932	30744
933	29659
934	29069
935	29445
936	29514
937	30171
938	31216
939	30139
940	27880
941	26682
942	28211
943	27876
944	28839
945	29390
946	27949
947	28206
948	28278
949	27115
950	27356
951	28146
952	28091
953	26952
954	28389
955	30549
956	31058
957	29410
958	29225
959	29684
960	30715
961	30941
962	29176
963	28303
964	28972
965	27470
966	27372
967	27407
968	29489
969	27701
970	26069
971	25646
972	25854
973	26148
974	25889
975	26474
976	26867
977	25084
978	23997
979	25027
980	25816
981	27020
982	27063
983	25156
984	24907
985	24425
986	24778
987	24734
988	24812
989	24614
990	24906
991	25340
992	25065
993	26047
994	24326
995	23485
996	24403
997	25549
998	26040
999	25816
1000	24414
1001	23704
1002	26006
1003	26522
1004	24462
1005	24871
1006	25940
1007	26007
1008	24703
1009	23701
1010	23881
1011	24185
1012	25043
1013	25857
1014	25570
1015	24501
1016	24312
1017	25169
1018	24970
1019	25496
1020	26358
1021	25770
1022	24795
1023	23931
1024	25150