1	9760
2	9428
3	9594
4	10628
5	11367
6	11465
7	11134
8	10522
9	10031
10	9609
11	9732
12	9418
13	9145
14	9034
15	8890
16	9727
17	10794
18	11193
19	10598
20	9999
21	10566
22	10764
23	11773
24	12213
25	11819
26	10633
27	9601
28	9493
29	9860
30	10179
31	10237
32	9990
33	10353
34	10258
35	9691
36	9919
37	10322
38	10379
39	10389
40	10225
41	10220
42	10075
43	10206
44	10620
45	11439
46	11523
47	11021
48	10528
49	10678
50	11321
51	12709
52	13737
53	14085
54	13297
55	12241
56	11097
57	11347
58	11883
59	11997
60	12489
61	12179
62	12265
63	12386
64	12207
65	12083
66	12615
67	12796
68	12714
69	12270
70	12034
71	10809
72	10735
73	11416
74	12250
75	13309
76	13904
77	13329
78	12678
79	12032
80	11869
81	12796
82	13492
83	15154
84	15752
85	16031
86	15401
87	14315
88	13295
89	12612
90	13440
91	14872
92	15811
93	15656
94	14234
95	13030
96	12307
97	11393
98	10949
99	10875
100	11062
101	11325
102	13100
103	15038
104	16350
105	16808
106	16381
107	14742
108	14172
109	14510
110	15985
111	16234
112	14469
113	12764
114	11247
115	11009
116	11543
117	12240
118	12668
119	14173
120	15027
121	14832
122	14481
123	14413
124	15130
125	16244
126	16584
127	15979
128	15228
129	15723
130	16464
131	17302
132	16924
133	15965
134	14724
135	14877
136	14880
137	15025
138	15373
139	15863
140	16065
141	15595
142	15450
143	16071
144	15539
145	14845
146	14593
147	15447
148	16649
149	16680
150	16944
151	17119
152	17424
153	17327
154	18051
155	17042
156	16020
157	15405
158	16089
159	15702
160	15450
161	15685
162	15829
163	15848
164	15862
165	15584
166	15887
167	15401
168	15570
169	15876
170	15700
171	16315
172	16560
173	17016
174	17833
175	17620
176	17225
177	17830
178	18344
179	17783
180	18178
181	18517
182	17938
183	17456
184	17143
185	17772
186	19040
187	19031
188	18050
189	17032
190	16663
191	16265
192	16595
193	17334
194	17280
195	17690
196	17641
197	18043
198	17542
199	17025
200	17392
201	17962
202	17745
203	18306
204	19263
205	19330
206	19427
207	18812
208	18203
209	18012
210	18407
211	18832
212	18604
213	19022
214	20754
215	22361
216	21952
217	21210
218	21488
219	20639
220	20593
221	21938
222	21738
223	20979
224	19952
225	20007
226	20924
227	21693
228	21684
229	21026
230	20531
231	20462
232	21299
233	21521
234	21536
235	21019
236	20429
237	20125
238	20643
239	20924
240	20885
241	21031
242	20465
243	20957
244	23062
245	24016
246	23128
247	21595
248	19965
249	18561
250	18584
251	19102
252	20306
253	21568
254	22456
255	24200
256	24913
257	25037
258	24095
259	23616
260	23600
261	23965
262	23714
263	24424
264	24509
265	25107
266	24090
267	23207
268	22531
269	23812
270	24474
271	24992
272	24787
273	25261
274	25048
275	25032
276	25727
277	24980
278	24725
279	25957
280	26851
281	26041
282	25629
283	25407
284	23665
285	23172
286	22738
287	22628
288	22506
289	21427
290	20641
291	20956
292	21697
293	22371
294	22947
295	22754
296	21935
297	22256
298	23930
299	26608
300	27958
301	28482
302	28163
303	28288
304	29131
305	28183
306	28423
307	29448
308	29688
309	29553
310	30314
311	28930
312	28385
313	28465
314	28167
315	27585
316	26464
317	26790
318	27364
319	29200
320	30492
321	31157
322	31720
323	31474
324	33068
325	34877
326	34888
327	34436
328	32610
329	32827
330	32430
331	31684
332	31081
333	30610
334	29779
335	30573
336	32258
337	32650
338	31023
339	29936
340	29620
341	30755
342	31294
343	31180
344	30024
345	29755
346	30579
347	31670
348	31108
349	31203
350	32932
351	32040
352	32174
353	33894
354	35075
355	34868
356	34182
357	32294
358	31500
359	34025
360	37520
361	38979
362	39268
363	39126
364	37149
365	36763
366	35694
367	36159
368	38050
369	39702
370	40526
371	40447
372	39461
373	39931
374	40407
375	40331
376	39949
377	38910
378	40422
379	42513
380	43733
381	41815
382	40439
383	39771
384	40686
385	41477
386	42755
387	45847
388	46686
389	47765
390	47906
391	44817
392	42044
393	41206
394	40990
395	41433
396	43671
397	44120
398	45250
399	45698
400	46481
401	44981
402	43965
403	43213
404	43018
405	44268
406	48115
407	47997
408	50328
409	50428
410	49300
411	48594
412	51204
413	52587
414	52340
415	49612
416	49669
417	52128
418	56008
419	55951
420	54721
421	54486
422	54727
423	55017
424	53451
425	53821
426	57264
427	55236
428	53974
429	51259
430	55566
431	58296
432	59018
433	60255
434	61004
435	57518
436	56560
437	58953
438	62337
439	64976
440	62687
441	59385
442	58922
443	64660
444	69543
445	68499
446	64337
447	61629
448	63390
449	63486
450	64302
451	65121
452	67251
453	65366
454	67012
455	67809
456	68216
457	70297
458	71245
459	70464
460	69040
461	70105
462	73146
463	74802
464	73469
465	72232
466	70788
467	71137
468	72174
469	74590
470	75521
471	75050
472	74559
473	72431
474	75483
475	78882
476	77702
477	77745
478	79107
479	83050
480	85434
481	86597
482	86896
483	88291
484	87018
485	86304
486	88973
487	89867
488	89656
489	89147
490	89155
491	91554
492	89319
493	88521
494	89587
495	92157
496	94890
497	95079
498	97864
499	101984
500	105214
501	105057
502	105338
503	104717
504	103611
505	101331
506	101568
507	103635
508	107911
509	109724
510	110554
511	108575
512	105628
513	108296
514	111572
515	110758
516	106958
517	104941
518	109562
519	113726
520	117297
521	116426
522	114908
523	113706
524	110716
525	109684
526	116089
527	119191
528	116749
529	117060
530	123318
531	128492
532	128481
533	128855
534	125562
535	126338
536	124985
537	123611
538	126881
539	127277
540	127707
541	129985
542	130061
543	129380
544	133193
545	140414
546	142452
547	137094
548	132520
549	130835
550	132663
551	134992
552	137625
553	134938
554	132498
555	132876
556	129019
557	130240
558	135504
559	139511
560	142086
561	140276
562	142020
563	137690
564	138230
565	145181
566	147895
567	145353
568	144528
569	145854
570	145287
571	145247
572	149161
573	150309
574	148869
575	145329
576	140399
577	140831
578	141107
579	142335
580	140164
581	137952
582	138010
583	141867
584	139399
585	135334
586	137817
587	149162
588	153805
589	152234
590	147550
591	138080
592	136626
593	133949
594	133553
595	134963
596	139730
597	139688
598	136420
599	133826
600	132548
601	130914
602	125412
603	125919
604	126609
605	122463
606	120380
607	122028
608	117070
609	117992
610	120330
611	120418
612	118564
613	117741
614	118249
615	116461
616	113630
617	112367
618	109934
619	109062
620	108604
621	109923
622	109184
623	110954
624	111498
625	108695
626	105113
627	103027
628	103440
629	105033
630	108175
631	109800
632	106636
633	103168
634	99518
635	102233
636	100064
637	99926
638	97846
639	97061
640	95411
641	94529
642	94747
643	97290
644	96612
645	97179
646	93962
647	92076
648	95076
649	94189
650	92990
651	89785
652	86453
653	84839
654	89052
655	94112
656	90711
657	88167
658	87399
659	86037
660	82077
661	80717
662	82521
663	81966
664	79843
665	80374
666	80053
667	77288
668	74828
669	72227
670	72021
671	70820
672	74745
673	78084
674	74278
675	70660
676	71597
677	70570
678	68869
679	68856
680	68688
681	63172
682	63101
683	65318
684	67376
685	69634
686	64534
687	63621
688	61431
689	61432
690	61350
691	58894
692	55637
693	55387
694	56200
695	61169
696	61284
697	61274
698	58384
699	54184
700	54455
701	58615
702	62464
703	60052
704	57324
705	57624
706	59012
707	57456
708	57651
709	55152
710	53016
711	52086
712	51306
713	50649
714	48750
715	46138
716	47893
717	52903
718	53291
719	50995
720	48294
721	46680
722	48389
723	49446
724	47740
725	46455
726	46917
727	46969
728	46342
729	45749
730	43407
731	43968
732	47778
733	49035
734	46424
735	44399
736	45546
737	46820
738	44301
739	43013
740	44529
741	45593
742	46268
743	46275
744	47205
745	44191
746	42557
747	43920
748	45722
749	44666
750	40113
751	36920
752	37847
753	39639
754	39327
755	39332
756	37533
757	36641
758	36896
759	40133
760	40729
761	39352
762	41599
763	39148
764	35382
765	34392
766	34186
767	35014
768	35687
769	34909
770	31977
771	33655
772	35565
773	36024
774	36708
775	34995
776	32920
777	31683
778	29572
779	28235
780	29143
781	31825
782	32912
783	33123
784	35042
785	35788
786	36871
787	35652
788	32398
789	30943
790	31582
791	34023
792	37355
793	37313
794	36179
795	34785
796	32883
797	32687
798	33250
799	33355
800	32983
801	33864
802	32323
803	33130
804	32719
805	31751
806	28838
807	28683
808	28831
809	30776
810	29556
811	29228
812	30198
813	32712
814	31408
815	28498
816	27345
817	26202
818	26876
819	29288
820	30177
821	29148
822	27926
823	29525
824	30111
825	30635
826	28628
827	27879
828	25993
829	25637
830	26800
831	28320
832	29191
833	28464
834	28651
835	25946
836	24195
837	25771
838	29546
839	29865
840	29404
841	30746
842	29779
843	26744
844	25840
845	27496
846	28146
847	28578
848	27293
849	24357
850	21885
851	22791
852	22986
853	24614
854	23817
855	23287
856	23572
857	23290
858	22050
859	24133
860	23015
861	24340
862	25820
863	24385
864	23807
865	24780
866	22863
867	20473
868	19633
869	17766
870	19903
871	21942
872	23385
873	22795
874	22310
875	25050
876	25624
877	25739
878	25041
879	24539
880	24682
881	22346
882	22817
883	22393
884	22037
885	24352
886	24358
887	25753
888	26411
889	23180
890	22435
891	25458
892	23679
893	22583
894	23117
895	21925
896	21593
897	19398
898	18422
899	19682
900	21255
901	21195
902	22685
903	21583
904	20378
905	20659
906	21306
907	18865
908	18647
909	18726
910	20053
911	18898
912	19034
913	19161
914	17680
915	17982
916	20276
917	22469
918	21124
919	20678
920	20492
921	20555
922	19907
923	18364
924	18821
925	19344
926	19476
927	20116
928	19095
929	19016
930	19338
931	19242
932	20509
933	18957
934	17225
935	17409
936	16409
937	16995
938	18783
939	19186
940	20395
941	20406
942	19216
943	17616
944	18434
945	18760
946	17404
947	19435
948	21603
949	19461
950	16439
951	16720
952	16545
953	16941
954	17792
955	18162
956	19187
957	18156
958	17770
959	17329
960	18283
961	17002
962	17762
963	19822
964	18891
965	17213
966	16197
967	15934
968	15455
969	15214
970	14652
971	15357
972	16706
973	15260
974	13471
975	13350
976	15032
977	16102
978	15226
979	15548
980	14175
981	13595
982	15838
983	15500
984	15269
985	16314
986	15442
987	14060
988	14928
989	14809
990	14024
991	15603
992	17204
993	15251
994	14181
995	15488
996	13771
997	13199
998	14295
999	14197
1000	13338
1001	14512
1002	15760
1003	14883
1004	13788
1005	14093
1006	14433
1007	14823
1008	15836
1009	14144
1010	12969
1011	11889
1012	14263
1013	16283
1014	16873
1015	16577
1016	15761
1017	17350
1018	17638
1019	14632
1020	15182
1021	14124
1022	13460
1023	12919
1024	12989