1	20089
2	20837
3	20980
4	19662
5	18564
6	18085
7	18157
8	18695
9	18484
10	18509
11	18418
12	17943
13	17968
14	18368
15	18759
16	19607
17	19642
18	19741
19	20020
20	19399
21	18954
22	19238
23	19336
24	19853
25	21356
26	22265
27	22810
28	22447
29	21962
30	21293
31	21148
32	20638
33	19934
34	18420
35	16657
36	15336
37	14673
38	15363
39	17798
40	20279
41	22826
42	24135
43	22069
44	19169
45	18412
46	17713
47	18177
48	18357
49	19185
50	18724
51	18766
52	18299
53	17553
54	17521
55	18117
56	19288
57	19592
58	18135
59	17044
60	16881
61	17052
62	17694
63	18795
64	20037
65	21168
66	22107
67	20584
68	19807
69	19140
70	18949
71	19015
72	18258
73	17583
74	16759
75	17238
76	18486
77	19574
78	20093
79	20437
80	20607
81	20280
82	20015
83	19488
84	19372
85	18682
86	18242
87	17687
88	18536
89	18663
90	19356
91	19493
92	20028
93	22764
94	25065
95	25410
96	24705
97	23925
98	21886
99	20750
100	19768
101	19055
102	19411
103	21312
104	22210
105	22060
106	21390
107	21104
108	21207
109	20656
110	21075
111	20658
112	20072
113	19193
114	20380
115	21391
116	22337
117	22071
118	21601
119	21020
120	21045
121	21234
122	21223
123	21602
124	22198
125	24052
126	24627
127	23628
128	23006
129	22647
130	23391
131	23599
132	22862
133	21974
134	22067
135	21688
136	21851
137	21197
138	20905
139	19666
140	18957
141	18529
142	18767
143	19440
144	19848
145	20772
146	21615
147	22895
148	23010
149	23130
150	22365
151	21141
152	20554
153	19434
154	20012
155	20614
156	20027
157	18200
158	16895
159	18114
160	19989
161	21498
162	22006
163	21869
164	22401
165	21844
166	20427
167	19225
168	18651
169	17795
170	17090
171	15847
172	15706
173	16385
174	17994
175	19137
176	20078
177	20845
178	21691
179	22192
180	22434
181	21945
182	21881
183	22945
184	23756
185	24038
186	24799
187	25849
188	25808
189	24947
190	23937
191	23436
192	22494
193	23304
194	22255
195	22119
196	22422
197	24597
198	25765
199	25994
200	23914
201	22710
202	22007
203	22796
204	23421
205	22785
206	23180
207	25033
208	25281
209	24205
210	21251
211	19576
212	19361
213	20989
214	22523
215	22534
216	20803
217	19283
218	20960
219	23803
220	25266
221	23333
222	20859
223	21261
224	22556
225	24024
226	24042
227	22767
228	21297
229	20167
230	18791
231	17447
232	16332
233	17285
234	18033
235	19380
236	21165
237	22685
238	23827
239	23232
240	21773
241	20147
242	20276
243	22003
244	23173
245	24585
246	25911
247	27291
248	29253
249	29772
250	27623
251	24775
252	22996
253	23118
254	23977
255	23847
256	23184
257	23394
258	24715
259	24926
260	23763
261	22913
262	22134
263	22463
264	22824
265	23439
266	25227
267	24830
268	23770
269	22173
270	21497
271	23456
272	23584
273	19881
274	16569
275	17236
276	19292
277	22498
278	27123
279	29775
280	27849
281	24893
282	23090
283	22875
284	24459
285	25146
286	24123
287	22527
288	19968
289	18981
290	18676
291	19796
292	22059
293	25204
294	27257
295	26800
296	25085
297	24078
298	24962
299	26124
300	24755
301	22983
302	21389
303	20696
304	20604
305	21484
306	22389
307	22873
308	23880
309	24802
310	26045
311	26216
312	24049
313	23976
314	25250
315	27239
316	27651
317	27327
318	25282
319	21785
320	19821
321	20912
322	22976
323	25026
324	26005
325	25652
326	26236
327	29150
328	30917
329	28766
330	26185
331	25255
332	26579
333	26622
334	25942
335	26490
336	29010
337	31003
338	29334
339	25538
340	22714
341	22766
342	23979
343	25417
344	24852
345	24069
346	23262
347	23782
348	24751
349	26226
350	27219
351	27076
352	27593
353	29986
354	31472
355	29554
356	26535
357	25498
358	27111
359	26731
360	25184
361	24601
362	25847
363	26902
364	27594
365	28100
366	28607
367	27892
368	27429
369	27256
370	28146
371	29360
372	30303
373	33812
374	36211
375	36454
376	35129
377	34548
378	34275
379	32529
380	31246
381	29349
382	28434
383	27944
384	29573
385	32501
386	34380
387	33597
388	32368
389	33712
390	36469
391	37247
392	36622
393	36403
394	34437
395	34966
396	37175
397	38527
398	37772
399	33603
400	30161
401	27691
402	26600
403	26860
404	30080
405	34588
406	37686
407	36163
408	33534
409	33025
410	34406
411	33834
412	34826
413	35863
414	34394
415	30238
416	28825
417	29817
418	34105
419	40580
420	43771
421	44603
422	42801
423	40353
424	38304
425	38563
426	41853
427	43043
428	42341
429	41289
430	40765
431	38740
432	35832
433	36091
434	36922
435	37997
436	36784
437	36808
438	38359
439	38636
440	37527
441	37274
442	38710
443	40447
444	44398
445	46727
446	46464
447	42766
448	38281
449	35950
450	35498
451	34294
452	33978
453	34729
454	37436
455	38737
456	39018
457	40128
458	41704
459	42252
460	41789
461	41552
462	39535
463	39274
464	41132
465	42292
466	40753
467	39664
468	40708
469	46901
470	49213
471	47500
472	44187
473	44066
474	46716
475	49158
476	50878
477	50444
478	48030
479	44815
480	42127
481	40736
482	42131
483	44720
484	48167
485	49540
486	47541
487	44089
488	43627
489	45240
490	48461
491	51848
492	53945
493	56087
494	57651
495	60373
496	60186
497	57772
498	57922
499	59023
500	63248
501	66470
502	64617
503	60907
504	57889
505	53465
506	54299
507	61788
508	67807
509	69012
510	66483
511	65836
512	69012
513	73266
514	73732
515	68840
516	63152
517	59833
518	62048
519	63216
520	65267
521	67563
522	69636
523	70289
524	72390
525	76938
526	80790
527	78676
528	75347
529	73034
530	71114
531	69478
532	67627
533	67836
534	68867
535	71888
536	75514
537	80001
538	85471
539	88335
540	91217
541	95125
542	96656
543	96922
544	96619
545	96863
546	97469
547	94831
548	91330
549	90632
550	94547
551	98765
552	101795
553	104186
554	103888
555	103030
556	103910
557	108179
558	111129
559	115789
560	123633
561	125235
562	127686
563	127317
564	132844
565	138277
566	141852
567	143026
568	146054
569	153062
570	167458
571	174729
572	170934
573	161522
574	157440
575	163696
576	170041
577	169546
578	172437
579	179392
580	191364
581	200622
582	201393
583	195982
584	196183
585	201022
586	202786
587	208673
588	220774
589	237528
590	242455
591	243478
592	242954
593	247456
594	256591
595	266838
596	284177
597	296231
598	295270
599	293600
600	302556
601	312839
602	315932
603	326247
604	350991
605	367711
606	372126
607	376741
608	386813
609	404812
610	427258
611	452027
612	469197
613	470565
614	479285
615	483973
616	485324
617	503195
618	517885
619	541971
620	567898
621	600338
622	624166
623	631881
624	640006
625	662746
626	689353
627	715452
628	773057
629	802646
630	815813
631	840587
632	861775
633	879786
634	895665
635	907599
636	920616
637	938890
638	943394
639	946935
640	948697
641	959561
642	958535
643	976215
644	974387
645	972811
646	975899
647	986253
648	1029232
649	1046342
650	1054078
651	1056263
652	1035985
653	1016978
654	1012256
655	1018961
656	1003387
657	991389
658	989714
659	981811
660	976030
661	971530
662	969131
663	948130
664	947291
665	958585
666	962673
667	955875
668	942056
669	946442
670	953315
671	949957
672	933338
673	921851
674	916589
675	877793
676	843439
677	802208
678	753854
679	729386
680	725215
681	700538
682	667282
683	643844
684	624025
685	610032
686	584545
687	554044
688	503919
689	488760
690	483473
691	453643
692	419662
693	403380
694	392536
695	388133
696	388942
697	367359
698	344078
699	320355
700	309590
701	308682
702	307227
703	311021
704	311952
705	298936
706	278686
707	258261
708	242512
709	237276
710	232183
711	226097
712	225918
713	223891
714	216553
715	214210
716	210541
717	204699
718	199824
719	191244
720	183010
721	172385
722	173136
723	168287
724	163309
725	159971
726	152070
727	143293
728	146555
729	154511
730	158302
731	155900
732	141747
733	135230
734	127617
735	120769
736	119144
737	125425
738	128726
739	130177
740	123449
741	124971
742	129312
743	113995
744	105808
745	108560
746	109143
747	104619
748	103509
749	105543
750	105797
751	108157
752	107733
753	102874
754	98999
755	100016
756	94482
757	92066
758	89836
759	88467
760	84413
761	82630
762	85321
763	88947
764	86798
765	89346
766	93536
767	92693
768	86981
769	83155
770	84518
771	82882
772	84759
773	78669
774	73308
775	75808
776	79420
777	80905
778	83176
779	84668
780	80109
781	71486
782	67673
783	68904
784	72779
785	72887
786	70012
787	69515
788	68320
789	66726
790	69670
791	66535
792	62861
793	61932
794	62147
795	60024
796	63230
797	63447
798	60180
799	57214
800	52561
801	54427
802	59162
803	57583
804	55916
805	56204
806	52779
807	48815
808	45330
809	43620
810	43470
811	43602
812	47142
813	49529
814	46559
815	45576
816	46375
817	46163
818	43569
819	49593
820	59259
821	59557
822	51801
823	49692
824	50640
825	47920
826	42765
827	43706
828	48737
829	49568
830	41125
831	37048
832	38556
833	38283
834	35892
835	35756
836	37274
837	41367
838	42622
839	44790
840	43433
841	41105
842	40097
843	36544
844	36125
845	33411
846	33183
847	37262
848	40646
849	42634
850	41462
851	39224
852	34890
853	37517
854	41169
855	39409
856	35308
857	32178
858	30139
859	30316
860	33741
861	35776
862	36048
863	32576
864	30139
865	31654
866	35928
867	30555
868	25958
869	24715
870	26968
871	32763
872	32660
873	34220
874	37521
875	38564
876	35586
877	32368
878	27349
879	28527
880	31794
881	31668
882	32999
883	32613
884	32305
885	31873
886	29615
887	29315
888	28022
889	24553
890	23894
891	21651
892	24102
893	29414
894	31121
895	31059
896	36483
897	32348
898	23921
899	23089
900	27881
901	29231
902	30850
903	34479
904	31100
905	26756
906	25650
907	27195
908	31984
909	29010
910	25690
911	23520
912	23551
913	24368
914	28935
915	29452
916	24587
917	22924
918	20727
919	23285
920	25995
921	24276
922	23088
923	22959
924	23942
925	26522
926	26711
927	27824
928	27643
929	27948
930	29114
931	29829
932	27327
933	26647
934	23834
935	22731
936	23052
937	28038
938	28530
939	30561
940	32092
941	29922
942	25585
943	26523
944	23359
945	19626
946	19457
947	20707
948	24812
949	26569
950	23460
951	20638
952	24952
953	26539
954	25714
955	22326
956	20672
957	19501
958	20916
959	22727
960	20880
961	19316
962	21291
963	23514
964	28054
965	27527
966	24778
967	23678
968	23812
969	23425
970	21202
971	21322
972	22173
973	22977
974	22771
975	19271
976	20712
977	20981
978	20238
979	20534
980	23555
981	24810
982	25290
983	25870
984	25815
985	25782
986	25727
987	24834
988	16481
989	17765
990	20843
991	21068
992	18316
993	17277
994	20046
995	21828
996	23662
997	28610
998	24775
999	20559
1000	18508
1001	20168
1002	22293
1003	25374
1004	24563
1005	20868
1006	21403
1007	25750
1008	28199
1009	23825
1010	18354
1011	16355
1012	15804
1013	16693
1014	17951
1015	19337
1016	17103
1017	15252
1018	14149
1019	13894
1020	19150
1021	23637
1022	22058
1023	19207
1024	16771