1	9595
2	10373
3	11500
4	12267
5	12252
6	11631
7	11642
8	11095
9	10445
10	10086
11	10207
12	10099
13	10040
14	10352
15	10649
16	10966
17	10880
18	10247
19	9876
20	9436
21	9591
22	9265
23	9198
24	8893
25	9220
26	9735
27	9540
28	10277
29	10932
30	12062
31	12555
32	12092
33	11557
34	10973
35	10877
36	10894
37	10743
38	10633
39	11002
40	11447
41	10987
42	11566
43	12252
44	13168
45	13315
46	12755
47	12611
48	12512
49	12025
50	11364
51	11004
52	11527
53	11145
54	11685
55	11917
56	11254
57	11132
58	11614
59	12092
60	12516
61	12668
62	12872
63	13187
64	12658
65	11463
66	11211
67	11856
68	12648
69	12628
70	12261
71	12059
72	11709
73	11779
74	12462
75	13529
76	13700
77	13802
78	13550
79	12645
80	11847
81	11317
82	10410
83	10270
84	10777
85	11646
86	12848
87	14090
88	14517
89	13526
90	13558
91	12944
92	14191
93	15067
94	15188
95	14468
96	13229
97	12359
98	12352
99	12534
100	12699
101	12483
102	12552
103	11804
104	11415
105	10918
106	11313
107	11806
108	12073
109	11635
110	11834
111	12611
112	13318
113	13952
114	13978
115	14289
116	13831
117	13679
118	13214
119	12993
120	13048
121	13651
122	13671
123	13077
124	12400
125	11919
126	12263
127	13404
128	13821
129	14042
130	13658
131	13030
132	12402
133	12480
134	12699
135	12781
136	12882
137	13653
138	13643
139	13194
140	12952
141	13545
142	14663
143	15295
144	14956
145	14809
146	13766
147	13188
148	13324
149	13831
150	13777
151	13289
152	13085
153	13027
154	13250
155	13365
156	13453
157	13966
158	14518
159	15153
160	15295
161	15419
162	14858
163	14716
164	15475
165	16577
166	16320
167	15837
168	15750
169	15240
170	15290
171	16237
172	16681
173	17529
174	17550
175	17661
176	15869
177	13642
178	14074
179	15662
180	16628
181	16860
182	16367
183	16216
184	16750
185	17982
186	19072
187	19314
188	19025
189	18095
190	17602
191	17142
192	17419
193	17425
194	17852
195	17463
196	17861
197	18511
198	18353
199	17229
200	15466
201	14977
202	14848
203	14008
204	14508
205	16225
206	17616
207	17631
208	17809
209	17682
210	17118
211	18277
212	18749
213	18936
214	19257
215	19259
216	18644
217	18720
218	18968
219	19364
220	18407
221	17993
222	17527
223	16938
224	15572
225	15922
226	16134
227	16754
228	17622
229	19911
230	20241
231	20429
232	19930
233	19176
234	19083
235	19351
236	19933
237	20060
238	19970
239	19355
240	18442
241	17193
242	16050
243	16163
244	17194
245	18709
246	19565
247	19834
248	19667
249	20071
250	20448
251	20577
252	21732
253	23546
254	24130
255	23006
256	22602
257	22019
258	22513
259	23633
260	23955
261	24835
262	25530
263	26439
264	26177
265	24760
266	23663
267	22278
268	21666
269	21602
270	20922
271	20958
272	21979
273	22324
274	23172
275	22714
276	21680
277	21785
278	23152
279	24699
280	24785
281	25358
282	24933
283	24984
284	25102
285	25081
286	24458
287	24346
288	24232
289	24708
290	25162
291	25092
292	25635
293	24889
294	24932
295	24756
296	23291
297	22174
298	22410
299	24288
300	25238
301	25283
302	24690
303	24649
304	24135
305	24435
306	25086
307	26255
308	27583
309	28703
310	30509
311	30310
312	28765
313	26330
314	25250
315	26214
316	27631
317	27496
318	26876
319	26354
320	26563
321	27497
322	28243
323	28093
324	29187
325	30111
326	30132
327	32468
328	33895
329	34249
330	33953
331	35366
332	35013
333	33702
334	33210
335	33119
336	31255
337	29083
338	28646
339	27512
340	26877
341	27514
342	27683
343	28340
344	28726
345	28324
346	28282
347	29017
348	30894
349	32285
350	33266
351	32773
352	31801
353	32498
354	32369
355	30983
356	31235
357	33362
358	35452
359	35593
360	35548
361	35544
362	36581
363	36132
364	35554
365	34744
366	33858
367	35109
368	36973
369	37364
370	36738
371	36792
372	37947
373	38544
374	38237
375	36300
376	34604
377	35130
378	36442
379	36890
380	36594
381	35485
382	34502
383	33100
384	32621
385	33595
386	35654
387	36530
388	37311
389	39539
390	40895
391	40723
392	40643
393	40549
394	39480
395	41910
396	44232
397	43735
398	42619
399	42168
400	42367
401	42823
402	43609
403	45267
404	46437
405	46190
406	45985
407	47460
408	49046
409	47431
410	46898
411	46728
412	46256
413	46079
414	46428
415	47950
416	47691
417	48126
418	50339
419	51016
420	49308
421	46079
422	46569
423	47737
424	49527
425	52595
426	54187
427	53492
428	53498
429	52955
430	54504
431	55430
432	55034
433	55471
434	55428
435	54558
436	54649
437	55932
438	57080
439	57572
440	58063
441	60060
442	62052
443	62514
444	62764
445	61650
446	61849
447	62929
448	66366
449	66816
450	64224
451	60482
452	61588
453	64284
454	65943
455	65960
456	65129
457	64705
458	64761
459	66087
460	65690
461	64375
462	65616
463	65433
464	65088
465	65107
466	66470
467	66777
468	68114
469	68864
470	66953
471	67938
472	70241
473	69910
474	69921
475	71913
476	72130
477	70433
478	74023
479	78867
480	80473
481	83649
482	88877
483	91395
484	85313
485	80749
486	81092
487	82544
488	83905
489	83479
490	83316
491	82887
492	82923
493	89709
494	95557
495	96209
496	95415
497	95466
498	91174
499	88825
500	89215
501	91687
502	95563
503	95971
504	94873
505	94227
506	94855
507	97493
508	101206
509	103612
510	106791
511	108913
512	109327
513	110351
514	108132
515	104029
516	99914
517	101490
518	107855
519	109857
520	107658
521	104263
522	107663
523	112620
524	111265
525	107754
526	105630
527	105096
528	104555
529	106703
530	105209
531	104431
532	105022
533	109977
534	108975
535	108424
536	112654
537	117295
538	123464
539	123184
540	120094
541	117687
542	119184
543	121558
544	124838
545	127881
546	124645
547	122548
548	121486
549	117519
550	120699
551	125513
552	124378
553	126338
554	126712
555	124580
556	122623
557	121025
558	130602
559	134255
560	134647
561	130935
562	129657
563	128156
564	132296
565	136226
566	139186
567	138419
568	140025
569	140427
570	142724
571	145071
572	140791
573	139661
574	141664
575	142324
576	139749
577	134956
578	133804
579	135224
580	141724
581	144620
582	138717
583	135469
584	137027
585	135977
586	132070
587	129035
588	128023
589	127653
590	132507
591	134689
592	135710
593	134067
594	130424
595	129108
596	130231
597	130722
598	132282
599	130077
600	127635
601	127653
602	128710
603	124889
604	117374
605	113533
606	116517
607	121283
608	123017
609	125001
610	120320
611	116180
612	118155
613	122708
614	118096
615	110780
616	107181
617	109212
618	109830
619	113148
620	112084
621	109633
622	108734
623	106201
624	106732
625	101545
626	96414
627	95532
628	96396
629	96926
630	100442
631	102613
632	101448
633	99201
634	94610
635	89883
636	90175
637	93670
638	90163
639	89185
640	89503
641	89886
642	86090
643	86394
644	87365
645	86589
646	86022
647	85491
648	84821
649	83354
650	83816
651	84468
652	83450
653	86663
654	86528
655	86416
656	87323
657	82084
658	78407
659	72304
660	74292
661	76232
662	76988
663	78768
664	77457
665	73432
666	70998
667	68234
668	68477
669	67410
670	65630
671	67125
672	67073
673	67976
674	67321
675	64291
676	65808
677	66069
678	64688
679	63500
680	61863
681	64198
682	63501
683	65123
684	64894
685	64210
686	61773
687	64330
688	66752
689	66805
690	61508
691	57693
692	59024
693	60343
694	57031
695	54591
696	56774
697	58543
698	55367
699	55414
700	57984
701	56144
702	54392
703	55967
704	55463
705	53992
706	52427
707	52824
708	52002
709	53051
710	54407
711	52841
712	51201
713	47861
714	48233
715	48878
716	48155
717	48576
718	48453
719	46044
720	44813
721	44226
722	44202
723	45412
724	46376
725	47609
726	46315
727	44660
728	43759
729	44790
730	48101
731	47706
732	46918
733	48732
734	46571
735	46228
736	47780
737	45320
738	42415
739	41343
740	39812
741	38359
742	40239
743	40519
744	41923
745	40461
746	39798
747	39966
748	40226
749	40823
750	39666
751	38408
752	37963
753	36871
754	36673
755	37411
756	35688
757	36166
758	36883
759	39072
760	37643
761	36391
762	38216
763	39210
764	36260
765	36663
766	37155
767	33287
768	31853
769	31060
770	31031
771	33225
772	33992
773	35487
774	36300
775	36471
776	36275
777	36724
778	36266
779	35290
780	36135
781	35206
782	35082
783	33836
784	31893
785	29983
786	29612
787	34888
788	35977
789	32137
790	30322
791	32070
792	32033
793	32096
794	29494
795	28777
796	27889
797	29143
798	27399
799	28837
800	28847
801	25446
802	25987
803	26992
804	26219
805	27388
806	27548
807	25990
808	26904
809	30615
810	29473
811	29659
812	27962
813	27375
814	28326
815	27682
816	28244
817	30133
818	29051
819	27456
820	26616
821	27704
822	27753
823	26962
824	27275
825	27808
826	25323
827	23615
828	26121
829	28111
830	28660
831	28698
832	27707
833	26634
834	25303
835	23079
836	19761
837	21155
838	22036
839	23389
840	26714
841	30024
842	26364
843	22297
844	22468
845	21412
846	22109
847	24359
848	23506
849	24837
850	24626
851	23583
852	23434
853	23906
854	21925
855	22899
856	23635
857	21670
858	20001
859	20691
860	21933
861	20422
862	20817
863	21369
864	21462
865	22433
866	23496
867	24778
868	26956
869	23137
870	20009
871	18097
872	16646
873	20177
874	22399
875	22542
876	19232
877	18384
878	19291
879	20624
880	21928
881	22512
882	21347
883	19101
884	17388
885	19075
886	22290
887	24679
888	20353
889	18653
890	18471
891	19775
892	20768
893	21694
894	19867
895	19549
896	17719
897	16845
898	17688
899	18949
900	20846
901	22309
902	20356
903	18280
904	17054
905	17527
906	19031
907	18285
908	17881
909	18174
910	19385
911	19456
912	18346
913	18767
914	18549
915	17656
916	17594
917	17424
918	16358
919	15826
920	13965
921	13660
922	15816
923	17153
924	17638
925	16019
926	17298
927	18308
928	16049
929	16842
930	17132
931	18799
932	18420
933	16822
934	15023
935	15050
936	18093
937	16633
938	17947
939	19763
940	16709
941	15914
942	16734
943	17400
944	19174
945	18986
946	17908
947	18242
948	17465
949	17397
950	17164
951	18905
952	19191
953	18080
954	17228
955	17738
956	16283
957	15286
958	14450
959	14916
960	14301
961	16341
962	17107
963	14946
964	13870
965	14980
966	14224
967	14204
968	14347
969	14712
970	15144
971	14682
972	14762
973	14452
974	14107
975	14070
976	14672
977	16433
978	17249
979	17203
980	16392
981	13416
982	13071
983	11970
984	11049
985	12534
986	14582
987	14838
988	15165
989	18568
990	20469
991	17938
992	16300
993	16346
994	16646
995	16785
996	16633
997	13865
998	14219
999	15490
1000	15179
1001	15749
1002	15199
1003	14755
1004	14562
1005	15955
1006	16835
1007	16328
1008	18172
1009	17569
1010	16012
1011	14301
1012	12886
1013	13944
1014	13888
1015	14887
1016	14916
1017	13306
1018	14069
1019	15761
1020	13944
1021	14659
1022	15378
1023	17901
1024	17918