1	8984
2	8140
3	8364
4	9310
5	11251
6	13635
7	15083
8	15190
9	14631
10	13618
11	12742
12	12598
13	13050
14	13535
15	13539
16	13521
17	13437
18	13859
19	14228
20	14569
21	14829
22	15905
23	16828
24	17599
25	17399
26	16893
27	15982
28	15153
29	14442
30	14447
31	14885
32	15262
33	15949
34	16590
35	16786
36	16499
37	16037
38	15353
39	15468
40	15745
41	15876
42	15884
43	16166
44	16417
45	17932
46	19606
47	20969
48	22620
49	23615
50	22531
51	20360
52	17949
53	16941
54	17358
55	18112
56	17580
57	16246
58	14779
59	13213
60	12433
61	13031
62	13986
63	15128
64	15347
65	15857
66	17174
67	19233
68	21292
69	22823
70	23220
71	24188
72	25389
73	26398
74	26379
75	26212
76	25611
77	25836
78	26282
79	26859
80	27483
81	27613
82	27957
83	30478
84	34824
85	39797
86	44531
87	47340
88	48719
89	51131
90	53709
91	56222
92	58253
93	58677
94	59462
95	62136
96	65420
97	67233
98	66972
99	63076
100	58813
101	52483
102	50300
103	48570
104	47797
105	46521
106	44071
107	40951
108	36832
109	31886
110	27629
111	24945
112	24120
113	24307
114	24274
115	23789
116	23095
117	22585
118	23167
119	24702
120	26063
121	27110
122	27296
123	26358
124	25583
125	23876
126	21479
127	18017
128	14970
129	13205
130	12997
131	13758
132	14100
133	14568
134	14045
135	14346
136	14782
137	16109
138	17382
139	17828
140	18537
141	18099
142	17156
143	16407
144	15615
145	15088
146	14553
147	14827
148	15777
149	17065
150	17864
151	17341
152	16704
153	16163
154	16707
155	17452
156	19028
157	20604
158	21759
159	22058
160	21958
161	22633
162	22976
163	22166
164	21726
165	20822
166	20428
167	19143
168	18099
169	18053
170	18044
171	18234
172	17727
173	16652
174	15092
175	14306
176	14984
177	16175
178	16632
179	16074
180	15107
181	14586
182	15268
183	16398
184	16246
185	16101
186	16095
187	16767
188	17741
189	18656
190	18715
191	17975
192	16773
193	16194
194	16731
195	18030
196	18741
197	18038
198	16677
199	15706
200	15041
201	14324
202	14591
203	15515
204	16908
205	18312
206	19198
207	19329
208	19139
209	18926
210	18930
211	19000
212	18852
213	19390
214	21038
215	21940
216	23151
217	24160
218	25081
219	26593
220	27993
221	29921
222	32665
223	35836
224	36959
225	36982
226	36921
227	37129
228	38817
229	40904
230	42667
231	42133
232	40934
233	38874
234	37458
235	36170
236	35306
237	35521
238	37230
239	37564
240	36386
241	33145
242	29194
243	26006
244	24184
245	25355
246	28068
247	29870
248	29308
249	26894
250	24286
251	22540
252	22340
253	23642
254	24746
255	25145
256	24635
257	24929
258	26026
259	27341
260	29406
261	31609
262	32444
263	32085
264	33273
265	35675
266	37446
267	37647
268	37489
269	36294
270	34355
271	31589
272	28855
273	27020
274	25356
275	24963
276	24596
277	25218
278	26845
279	28038
280	27510
281	24984
282	22323
283	21713
284	22677
285	22777
286	20728
287	18735
288	19350
289	21622
290	22200
291	20313
292	17684
293	16785
294	17375
295	19037
296	21001
297	21506
298	20893
299	20338
300	22440
301	26676
302	29560
303	29997
304	28692
305	26351
306	23753
307	22343
308	21525
309	20396
310	18939
311	17024
312	15807
313	15125
314	14991
315	14800
316	16198
317	18547
318	21337
319	22875
320	22608
321	22725
322	24668
323	28791
324	31200
325	31990
326	31795
327	32802
328	35536
329	37977
330	40318
331	42683
332	45740
333	47583
334	49326
335	53503
336	59367
337	65568
338	69294
339	69227
340	66048
341	62588
342	58717
343	54434
344	53273
345	54414
346	52377
347	48057
348	45965
349	45701
350	44963
351	45005
352	46088
353	46592
354	45367
355	41460
356	40505
357	42644
358	43457
359	39565
360	35624
361	34032
362	32109
363	29460
364	27796
365	26396
366	26804
367	27840
368	27818
369	25803
370	23451
371	23041
372	22588
373	21597
374	19679
375	18209
376	18669
377	19416
378	19241
379	17972
380	18456
381	19059
382	19353
383	18523
384	18196
385	19290
386	19922
387	19278
388	20046
389	22234
390	22798
391	21181
392	19076
393	18962
394	19746
395	19873
396	18240
397	17038
398	18199
399	19852
400	21686
401	23790
402	24840
403	24463
404	24079
405	23923
406	23207
407	22361
408	23099
409	23348
410	22950
411	22749
412	23352
413	22925
414	20750
415	17441
416	15967
417	17213
418	19120
419	18189
420	17815
421	20682
422	25136
423	26650
424	26303
425	27073
426	27518
427	25096
428	22626
429	21700
430	20909
431	21171
432	21312
433	21219
434	21029
435	20465
436	19063
437	16798
438	15888
439	16070
440	17138
441	18248
442	19724
443	20140
444	20071
445	20221
446	20395
447	20093
448	20271
449	20378
450	19471
451	18285
452	18318
453	20148
454	22512
455	22708
456	21754
457	21160
458	21488
459	21576
460	21849
461	23240
462	26180
463	29101
464	31404
465	34141
466	36012
467	35096
468	35112
469	39059
470	42739
471	44285
472	43227
473	48340
474	56757
475	61534
476	60476
477	57118
478	55261
479	56729
480	57552
481	54005
482	48320
483	44994
484	41508
485	34634
486	29755
487	28890
488	29259
489	30242
490	30836
491	29622
492	27705
493	27714
494	27422
495	26476
496	26983
497	27215
498	25977
499	21812
500	18230
501	15645
502	15022
503	16095
504	17013
505	18421
506	20211
507	21763
508	22716
509	23670
510	22526
511	19877
512	19135
513	20918
514	22135
515	21794
516	20613
517	21311
518	23603
519	25770
520	25728
521	23715
522	22729
523	23449
524	24120
525	23598
526	23488
527	24933
528	23934
529	22593
530	20512
531	19207
532	18890
533	19716
534	20770
535	22000
536	21142
537	21213
538	22633
539	24691
540	27637
541	27063
542	24144
543	21647
544	19872
545	18667
546	18938
547	20195
548	20206
549	20470
550	19104
551	16849
552	17435
553	17935
554	17701
555	16568
556	16938
557	18981
558	18865
559	17978
560	17801
561	17297
562	18147
563	18717
564	19340
565	19662
566	20169
567	21727
568	23593
569	21889
570	20071
571	22171
572	25009
573	24898
574	24041
575	24631
576	25737
577	26050
578	26754
579	27549
580	26030
581	24601
582	24735
583	25346
584	26071
585	25493
586	24466
587	26206
588	29214
589	30396
590	29568
591	28440
592	29948
593	32119
594	31170
595	32194
596	36109
597	35135
598	31857
599	32190
600	33252
601	32367
602	31514
603	29644
604	25404
605	24069
606	25916
607	29989
608	30289
609	31252
610	37617
611	38247
612	33910
613	34253
614	36863
615	38627
616	35515
617	34855
618	40227
619	43384
620	40469
621	39062
622	39769
623	41980
624	40510
625	36408
626	33815
627	31684
628	31377
629	33461
630	36133
631	36288
632	34894
633	36971
634	39936
635	42196
636	40801
637	39726
638	39736
639	38880
640	39445
641	41615
642	41351
643	42107
644	42139
645	40734
646	40595
647	43676
648	46978
649	45294
650	44229
651	46855
652	50405
653	52299
654	54692
655	54462
656	53482
657	54287
658	54465
659	56761
660	56462
661	54521
662	54876
663	61122
664	66857
665	72987
666	74188
667	67426
668	65080
669	72984
670	79335
671	79542
672	79062
673	85155
674	92830
675	92558
676	89578
677	86333
678	85608
679	86101
680	86743
681	90789
682	91068
683	93126
684	100481
685	108503
686	108978
687	107354
688	111841
689	114048
690	118517
691	119061
692	117694
693	114993
694	116303
695	120809
696	127414
697	128390
698	128058
699	126102
700	120094
701	121557
702	121063
703	116975
704	125814
705	137283
706	138590
707	132100
708	130608
709	131696
710	128021
711	122018
712	119043
713	119104
714	122149
715	130534
716	136183
717	139875
718	143464
719	150963
720	156169
721	147545
722	147367
723	149230
724	144412
725	136929
726	132783
727	123397
728	117907
729	118039
730	118365
731	113395
732	104273
733	96348
734	94677
735	94864
736	92500
737	92352
738	89928
739	84911
740	87463
741	91752
742	96428
743	94082
744	83885
745	78117
746	74174
747	67491
748	64548
749	63517
750	63800
751	65965
752	69842
753	67056
754	66137
755	69956
756	69469
757	63308
758	56940
759	61339
760	65022
761	65424
762	64598
763	63387
764	63158
765	65239
766	62798
767	62828
768	59122
769	53918
770	51711
771	51322
772	54189
773	56150
774	58445
775	60316
776	58922
777	54973
778	49170
779	51797
780	57836
781	56680
782	52721
783	57338
784	60872
785	58683
786	55193
787	51458
788	51109
789	52531
790	49759
791	53458
792	58512
793	64316
794	65314
795	61738
796	60482
797	51779
798	42793
799	42151
800	46652
801	51438
802	49816
803	47549
804	49426
805	48867
806	45208
807	44556
808	48389
809	52257
810	53408
811	49436
812	46973
813	46270
814	50818
815	51701
816	52741
817	53773
818	50423
819	51024
820	49503
821	49303
822	52920
823	54833
824	58825
825	53232
826	49838
827	52345
828	48837
829	46324
830	48930
831	49148
832	47369
833	44008
834	45813
835	46886
836	46563
837	43074
838	46212
839	46962
840	46269
841	44491
842	43176
843	45772
844	50116
845	45675
846	37994
847	35068
848	34096
849	33438
850	31696
851	33445
852	35596
853	36424
854	34492
855	31565
856	33969
857	35873
858	36037
859	34418
860	32724
861	32360
862	33524
863	32183
864	29115
865	24705
866	23404
867	27966
868	32105
869	31480
870	31944
871	31826
872	30325
873	34778
874	33545
875	29486
876	28947
877	29338
878	25829
879	26475
880	29358
881	27814
882	27019
883	29356
884	28589
885	25763
886	22620
887	25386
888	30309
889	28418
890	22823
891	23581
892	24738
893	20933
894	21070
895	22522
896	26161
897	28481
898	28344
899	25936
900	20369
901	18809
902	20949
903	23253
904	24445
905	27229
906	26328
907	24221
908	26628
909	28670
910	27239
911	27946
912	30362
913	30348
914	31956
915	32597
916	28835
917	22922
918	18215
919	18219
920	21333
921	22177
922	24426
923	27773
924	25940
925	24920
926	24241
927	26414
928	28041
929	26594
930	24790
931	23982
932	22551
933	19829
934	19999
935	20614
936	19321
937	19058
938	22372
939	25225
940	22921
941	20848
942	24183
943	21088
944	18852
945	20650
946	27233
947	25109
948	20293
949	23433
950	23940
951	26034
952	27807
953	27863
954	26105
955	23923
956	22596
957	26618
958	26586
959	24867
960	22939
961	21225
962	23184
963	22734
964	21290
965	18965
966	21034
967	23367
968	22235
969	25187
970	29180
971	27780
972	26331
973	19990
974	20589
975	23341
976	24474
977	21982
978	21456
979	19496
980	19814
981	19384
982	18023
983	21815
984	21380
985	20010
986	19912
987	20549
988	20950
989	24986
990	22820
991	19238
992	17923
993	17996
994	17597
995	21058
996	19631
997	18651
998	16269
999	16416
1000	17161
1001	19300
1002	19361
1003	20667
1004	16842
1005	13618
1006	14448
1007	18043
1008	17200
1009	18293
1010	20629
1011	22568
1012	19191
1013	17886
1014	14517
1015	15466
1016	19269
1017	20471
1018	19580
1019	13666
1020	10346
1021	12386
1022	17147
1023	22297
1024	26003