1	22675
2	21376
3	21056
4	20466
5	20682
6	21463
7	22858
8	23897
9	24288
10	23915
11	23011
12	21469
13	19864
14	18296
15	17917
16	19609
17	20998
18	22425
19	23094
20	23453
21	23856
22	24373
23	24344
24	24086
25	23570
26	23291
27	23312
28	23561
29	23506
30	25119
31	26869
32	29529
33	30265
34	29911
35	28411
36	27757
37	28785
38	29577
39	31207
40	30800
41	28976
42	26810
43	23618
44	22668
45	24009
46	24296
47	23625
48	22036
49	21561
50	23101
51	25676
52	27092
53	28376
54	28864
55	29804
56	30434
57	31632
58	31804
59	30943
60	30323
61	30751
62	31835
63	32833
64	32409
65	31844
66	31543
67	31986
68	33567
69	33687
70	33058
71	33164
72	33428
73	35975
74	40399
75	44699
76	45932
77	44373
78	40659
79	37391
80	36095
81	36154
82	38000
83	40965
84	43579
85	45217
86	47437
87	48409
88	50962
89	54651
90	58673
91	60871
92	62480
93	61988
94	60858
95	59673
96	58610
97	57568
98	56220
99	55024
100	54643
101	52443
102	52237
103	52935
104	54231
105	54521
106	53073
107	50320
108	47097
109	43888
110	41052
111	38188
112	37328
113	37154
114	36884
115	35927
116	33821
117	32975
118	32855
119	33345
120	34024
121	34178
122	32878
123	30928
124	28238
125	27201
126	27269
127	27794
128	28530
129	29042
130	29800
131	30263
132	30035
133	29856
134	29246
135	28863
136	28433
137	29260
138	29415
139	27957
140	26806
141	25693
142	25496
143	25893
144	26930
145	28142
146	29379
147	30116
148	31199
149	31246
150	31773
151	33472
152	35879
153	37558
154	39059
155	39874
156	40982
157	42042
158	41705
159	40578
160	37163
161	33982
162	32407
163	32386
164	33463
165	33736
166	34402
167	35034
168	35272
169	35270
170	33434
171	31515
172	29420
173	28927
174	29368
175	31809
176	34933
177	36702
178	36772
179	35613
180	35167
181	36085
182	36245
183	35668
184	35735
185	36067
186	35242
187	33039
188	30599
189	28418
190	25773
191	23935
192	23460
193	26165
194	30051
195	33278
196	32464
197	29362
198	26252
199	25428
200	25781
201	27238
202	28589
203	29448
204	31203
205	33049
206	32894
207	31617
208	29544
209	27217
210	27401
211	28779
212	28940
213	28004
214	27547
215	28353
216	29540
217	30449
218	31002
219	32769
220	33758
221	33878
222	33071
223	33725
224	35923
225	38372
226	40124
227	41836
228	45875
229	49300
230	50290
231	49312
232	49193
233	50746
234	53141
235	53768
236	52180
237	49403
238	47417
239	46294
240	47163
241	47645
242	47425
243	47859
244	49051
245	49687
246	51400
247	53640
248	56930
249	57178
250	54409
251	49018
252	46980
253	47327
254	48821
255	50246
256	51190
257	54979
258	60186
259	66410
260	68825
261	70744
262	73917
263	79317
264	86732
265	91867
266	93926
267	93513
268	94584
269	93354
270	93243
271	95310
272	99448
273	100052
274	93149
275	83646
276	73651
277	67677
278	64427
279	60727
280	56219
281	52192
282	50587
283	50111
284	48487
285	45867
286	43681
287	45057
288	46473
289	46625
290	44730
291	44507
292	44762
293	46998
294	49952
295	52207
296	52785
297	51895
298	50003
299	48887
300	49489
301	53270
302	56619
303	57166
304	56694
305	55988
306	56438
307	56595
308	54940
309	51539
310	48408
311	45753
312	45138
313	45923
314	48153
315	51087
316	55752
317	60034
318	63384
319	66729
320	68396
321	68335
322	69264
323	72286
324	75988
325	83117
326	91456
327	98936
328	101703
329	101997
330	106369
331	116617
332	132242
333	147761
334	157327
335	168938
336	182491
337	191696
338	194859
339	195828
340	198841
341	196826
342	188334
343	176645
344	165180
345	152188
346	143885
347	141278
348	141512
349	143245
350	140437
351	131346
352	121482
353	115385
354	114876
355	116542
356	116762
357	113774
358	108668
359	101243
360	94535
361	90946
362	87397
363	81388
364	75710
365	70681
366	65148
367	58696
368	53585
369	50119
370	48594
371	48792
372	49646
373	48681
374	46814
375	47043
376	49368
377	51848
378	51407
379	47973
380	47324
381	47086
382	45718
383	42694
384	38236
385	34912
386	35013
387	38977
388	44742
389	48374
390	48614
391	47581
392	46470
393	47042
394	47940
395	48040
396	45795
397	43728
398	44072
399	45731
400	47819
401	49599
402	50343
403	50763
404	50507
405	49734
406	50535
407	52067
408	56162
409	55937
410	52073
411	47098
412	46400
413	48902
414	51045
415	49343
416	43747
417	40481
418	41285
419	42872
420	43574
421	42878
422	40664
423	39205
424	40830
425	43340
426	45298
427	44810
428	44028
429	42992
430	42023
431	41071
432	42047
433	46143
434	50181
435	50309
436	47064
437	45367
438	46440
439	47526
440	49871
441	51089
442	48991
443	46873
444	46533
445	47230
446	48933
447	50216
448	52513
449	54670
450	55656
451	56349
452	56855
453	56454
454	59072
455	62618
456	63474
457	64239
458	67002
459	68837
460	67964
461	70136
462	75292
463	82303
464	90133
465	99152
466	101727
467	96997
468	96463
469	102905
470	108668
471	118273
472	124021
473	134215
474	139356
475	142657
476	139070
477	134248
478	134296
479	136470
480	134284
481	129809
482	119707
483	108361
484	104255
485	101164
486	96594
487	92795
488	89152
489	85521
490	78398
491	68386
492	60526
493	60104
494	60373
495	62605
496	62965
497	59899
498	58614
499	56773
500	52869
501	46975
502	43398
503	46331
504	51707
505	54108
506	53298
507	53227
508	55375
509	57017
510	57435
511	56873
512	57523
513	58267
514	59912
515	58465
516	54529
517	50335
518	49468
519	51485
520	52610
521	49758
522	45736
523	43094
524	40732
525	37707
526	37655
527	42053
528	44739
529	42084
530	37759
531	33458
532	30829
533	32055
534	34195
535	36091
536	40098
537	42680
538	39327
539	35981
540	37194
541	40376
542	40248
543	37093
544	35938
545	41216
546	46875
547	44207
548	37407
549	33809
550	34526
551	35645
552	36924
553	39480
554	39976
555	37039
556	33146
557	33525
558	35173
559	34703
560	32898
561	31788
562	33233
563	34467
564	35169
565	36941
566	38924
567	38714
568	39403
569	39736
570	40351
571	42127
572	44240
573	43467
574	41661
575	42214
576	46562
577	49922
578	50491
579	52822
580	53709
581	51633
582	49083
583	46691
584	47206
585	48450
586	49957
587	52517
588	52337
589	54282
590	58547
591	61706
592	63179
593	63565
594	62995
595	64118
596	66492
597	67219
598	65174
599	62074
600	61124
601	61770
602	58880
603	53893
604	53949
605	56994
606	56467
607	57388
608	61664
609	63809
610	62943
611	64702
612	66893
613	67384
614	66683
615	68443
616	71336
617	71690
618	70041
619	70011
620	70120
621	70968
622	67613
623	60294
624	58481
625	63415
626	66507
627	63539
628	62845
629	61679
630	59493
631	60765
632	62491
633	63606
634	63688
635	63044
636	61301
637	61438
638	60994
639	59282
640	61479
641	65489
642	65016
643	63594
644	64436
645	65505
646	68516
647	78760
648	80786
649	68131
650	66397
651	77060
652	85890
653	82892
654	76791
655	81118
656	85464
657	84836
658	83700
659	83783
660	81916
661	81953
662	82836
663	80539
664	80056
665	81975
666	91604
667	99834
668	99604
669	97428
670	94057
671	91151
672	89040
673	94935
674	101825
675	106045
676	105991
677	99234
678	100916
679	109920
680	110687
681	109123
682	114122
683	118790
684	114927
685	114769
686	118637
687	119563
688	122561
689	125569
690	128094
691	125079
692	124784
693	122978
694	117338
695	118077
696	124620
697	125361
698	125753
699	125546
700	128042
701	132486
702	135025
703	131522
704	126782
705	128636
706	130880
707	133306
708	136461
709	140849
710	138396
711	140042
712	141367
713	139354
714	135841
715	132528
716	132885
717	130301
718	132146
719	134067
720	141169
721	151501
722	143295
723	130168
724	130280
725	133646
726	131943
727	131751
728	127830
729	117892
730	114007
731	119019
732	122510
733	118066
734	109024
735	100375
736	98449
737	99981
738	94046
739	85016
740	79122
741	78227
742	89470
743	92131
744	82912
745	79681
746	81578
747	79993
748	82962
749	83317
750	78339
751	78461
752	79107
753	75768
754	76084
755	78901
756	76640
757	77806
758	80562
759	73401
760	64771
761	65429
762	66287
763	64492
764	61207
765	63006
766	65175
767	66467
768	67309
769	63663
770	61316
771	62699
772	62161
773	64886
774	68726
775	67824
776	57953
777	53891
778	55508
779	54611
780	56149
781	58232
782	62365
783	63570
784	62626
785	67917
786	74061
787	72819
788	69472
789	69525
790	66179
791	65394
792	65996
793	69505
794	70176
795	71338
796	71311
797	64332
798	59470
799	59523
800	64035
801	68506
802	70107
803	73832
804	77733
805	70999
806	62920
807	57161
808	63384
809	67949
810	67733
811	66064
812	62137
813	61858
814	62481
815	64876
816	65656
817	57783
818	54368
819	58724
820	58498
821	54302
822	53787
823	53256
824	52727
825	51523
826	52782
827	54204
828	55820
829	57907
830	54981
831	49373
832	49542
833	50631
834	49269
835	42768
836	43497
837	45854
838	46892
839	46377
840	41073
841	40697
842	42539
843	39990
844	42307
845	46562
846	44899
847	43229
848	44285
849	41191
850	42005
851	46455
852	43538
853	45318
854	48603
855	50788
856	49885
857	46362
858	42364
859	41150
860	37325
861	32812
862	33347
863	37120
864	36470
865	33483
866	31666
867	34086
868	38145
869	34972
870	35397
871	38867
872	44066
873	46732
874	46709
875	40958
876	33798
877	30280
878	32697
879	38712
880	40580
881	41478
882	40480
883	37019
884	37315
885	38621
886	39872
887	47181
888	48682
889	40520
890	38025
891	40233
892	39992
893	40272
894	36516
895	32430
896	26927
897	23263
898	27185
899	30782
900	32877
901	41271
902	49634
903	49786
904	44953
905	41203
906	41160
907	40179
908	44867
909	49152
910	52274
911	55172
912	55796
913	56154
914	58778
915	57086
916	50780
917	50729
918	49344
919	45118
920	38527
921	38811
922	37706
923	37946
924	45699
925	46161
926	48281
927	45242
928	40752
929	39337
930	40450
931	39764
932	38944
933	40477
934	38619
935	31550
936	26775
937	31250
938	35247
939	35356
940	33442
941	33183
942	37280
943	39423
944	40842
945	41129
946	38259
947	33602
948	34501
949	38344
950	41250
951	41428
952	40675
953	41055
954	37651
955	36609
956	33752
957	33804
958	34710
959	38908
960	39760
961	37292
962	39569
963	41810
964	35746
965	32429
966	32270
967	36462
968	40659
969	34342
970	32073
971	36203
972	33973
973	32375
974	32316
975	31666
976	31833
977	28722
978	27728
979	26959
980	28915
981	30140
982	28573
983	25164
984	25535
985	29008
986	31106
987	28198
988	28623
989	26345
990	27034
991	27509
992	24879
993	26834
994	28881
995	30525
996	24386
997	20833
998	24438
999	33970
1000	35041
1001	28581
1002	32472
1003	34504
1004	32848
1005	35155
1006	33358
1007	33237
1008	32162
1009	30633
1010	29133
1011	34299
1012	40439
1013	35170
1014	28709
1015	25822
1016	21396
1017	28274
1018	29363
1019	26234
1020	24746
1021	29812
1022	31631
1023	28657
1024	26804