1	26100
2	24863
3	24561
4	24594
5	24979
6	25320
7	25036
8	23713
9	22352
10	21334
11	21098
12	21909
13	23827
14	25096
15	25282
16	24646
17	23710
18	22942
19	22510
20	22991
21	23756
22	24997
23	26162
24	26558
25	26293
26	26325
27	26290
28	25874
29	24411
30	24265
31	24390
32	24891
33	24890
34	24382
35	24598
36	25742
37	27915
38	28672
39	28897
40	27460
41	26465
42	26386
43	26254
44	25897
45	26295
46	27071
47	28854
48	30895
49	31405
50	31221
51	31180
52	30781
53	30014
54	29514
55	30392
56	31283
57	31055
58	29326
59	27643
60	26760
61	26308
62	26671
63	27923
64	29436
65	30922
66	31042
67	30545
68	30294
69	30941
70	32894
71	36327
72	38191
73	37571
74	35771
75	34148
76	33564
77	34069
78	34340
79	34736
80	35113
81	36243
82	39239
83	42610
84	46111
85	48857
86	51868
87	54712
88	56919
89	57858
90	57663
91	57183
92	58279
93	58469
94	57697
95	56658
96	57350
97	58920
98	60854
99	60521
100	59556
101	55930
102	53550
103	50899
104	49319
105	49254
106	49458
107	49411
108	48085
109	44830
110	40984
111	37418
112	35809
113	34518
114	33951
115	33792
116	32462
117	30636
118	29660
119	30249
120	31270
121	31958
122	30741
123	30512
124	31272
125	32940
126	33869
127	32939
128	30767
129	28388
130	28019
131	28640
132	28981
133	27685
134	24949
135	24157
136	25070
137	26777
138	27283
139	25728
140	25272
141	26674
142	28996
143	31721
144	33317
145	33469
146	31856
147	30060
148	31092
149	33265
150	35735
151	37211
152	37384
153	37688
154	40921
155	44681
156	47440
157	47859
158	46378
159	43425
160	38951
161	35819
162	34691
163	34927
164	35266
165	34179
166	32169
167	30381
168	30663
169	31864
170	32502
171	33230
172	33463
173	33703
174	33919
175	33279
176	31262
177	29784
178	29955
179	30652
180	31531
181	32861
182	35119
183	35916
184	35122
185	34573
186	34148
187	33266
188	31587
189	29630
190	28598
191	28603
192	30648
193	31875
194	31614
195	31955
196	31593
197	31103
198	29812
199	29323
200	29305
201	29550
202	29584
203	29669
204	29286
205	29550
206	30343
207	31670
208	31537
209	30059
210	29300
211	30516
212	33042
213	35670
214	37840
215	38027
216	36543
217	35242
218	34794
219	36639
220	39438
221	41563
222	41495
223	41434
224	41224
225	43283
226	46425
227	48581
228	48924
229	47888
230	47157
231	47395
232	48654
233	49862
234	52068
235	56175
236	59956
237	59988
238	57195
239	52320
240	50532
241	50009
242	50502
243	52078
244	51405
245	48658
246	45651
247	43746
248	43054
249	42939
250	42803
251	42083
252	42662
253	43938
254	45886
255	47808
256	49296
257	50451
258	51537
259	54431
260	58888
261	67033
262	75061
263	78656
264	81869
265	84556
266	87941
267	87903
268	87852
269	85270
270	82168
271	79364
272	78981
273	80610
274	79087
275	77676
276	73221
277	68494
278	65353
279	61180
280	56368
281	52553
282	50621
283	47699
284	44758
285	43833
286	43499
287	43752
288	43808
289	43662
290	42370
291	42771
292	43485
293	43700
294	43413
295	43059
296	43301
297	44596
298	47552
299	51924
300	55974
301	59935
302	63998
303	67946
304	70176
305	68183
306	63237
307	60342
308	56484
309	50458
310	44476
311	41043
312	41087
313	42688
314	45730
315	49567
316	54180
317	57852
318	59086
319	59552
320	60931
321	63791
322	69505
323	75448
324	82287
325	87330
326	88012
327	90271
328	94022
329	101809
330	112211
331	121831
332	130790
333	140117
334	146946
335	156110
336	166916
337	178668
338	186506
339	189477
340	188058
341	186562
342	181494
343	172416
344	162783
345	152808
346	143984
347	140126
348	139324
349	139928
350	139672
351	140105
352	137865
353	128866
354	121932
355	116677
356	112290
357	105906
358	97596
359	89364
360	85160
361	82004
362	80345
363	80185
364	79603
365	75091
366	71180
367	67040
368	62815
369	60511
370	59693
371	57932
372	54603
373	52137
374	50297
375	48833
376	47037
377	43984
378	40950
379	40125
380	43846
381	47271
382	46968
383	44645
384	43793
385	45825
386	49622
387	52508
388	52772
389	49905
390	47513
391	47803
392	48305
393	45738
394	39983
395	36834
396	37430
397	42142
398	46569
399	48002
400	48232
401	51205
402	55614
403	59158
404	60788
405	60836
406	59184
407	56369
408	56525
409	54065
410	52342
411	54779
412	58162
413	56588
414	51778
415	45769
416	40710
417	39139
418	41498
419	43679
420	47008
421	49019
422	48932
423	48084
424	49731
425	49963
426	47759
427	44556
428	44267
429	47176
430	51417
431	54568
432	55706
433	52081
434	47739
435	44359
436	42885
437	43582
438	44833
439	43054
440	42405
441	44161
442	46583
443	47534
444	46220
445	45977
446	45650
447	46593
448	48994
449	52150
450	55335
451	57147
452	57395
453	58153
454	59136
455	60193
456	62338
457	66217
458	70071
459	73199
460	76674
461	80820
462	85919
463	89943
464	91882
465	93182
466	97846
467	102409
468	107056
469	114513
470	120568
471	128823
472	131189
473	138109
474	140843
475	149611
476	157116
477	158075
478	155395
479	149039
480	139527
481	130922
482	122289
483	112901
484	106077
485	98679
486	93113
487	86968
488	82538
489	79499
490	74340
491	67212
492	64033
493	69465
494	71365
495	65315
496	54475
497	45373
498	42844
499	43630
500	46431
501	48515
502	46586
503	43639
504	43326
505	44511
506	45732
507	45998
508	46382
509	47084
510	48018
511	48867
512	48720
513	47046
514	44614
515	43446
516	43136
517	43460
518	43178
519	40954
520	39162
521	38596
522	39148
523	40411
524	41318
525	39580
526	38540
527	41715
528	40138
529	36636
530	36486
531	36646
532	35610
533	34676
534	33700
535	33565
536	34155
537	35611
538	35362
539	31797
540	29612
541	30236
542	29431
543	28830
544	31132
545	33969
546	35082
547	35078
548	33726
549	32333
550	32545
551	34571
552	36356
553	37545
554	37559
555	36177
556	35317
557	35431
558	34354
559	34409
560	33183
561	31343
562	33856
563	36772
564	38205
565	38050
566	39988
567	43289
568	44172
569	41368
570	39763
571	40599
572	43513
573	45280
574	43055
575	42725
576	45571
577	45119
578	41656
579	42672
580	47281
581	51843
582	57570
583	62265
584	60362
585	55740
586	54642
587	56285
588	56350
589	52622
590	47266
591	47304
592	52595
593	58291
594	60395
595	61671
596	63237
597	62385
598	65723
599	67962
600	63345
601	61177
602	64168
603	70111
604	70934
605	66078
606	61245
607	61578
608	59102
609	58964
610	62793
611	71067
612	81451
613	83955
614	77554
615	72984
616	71955
617	75231
618	75751
619	72657
620	67460
621	64039
622	64161
623	65314
624	64753
625	66590
626	68316
627	65342
628	65935
629	71080
630	72868
631	67352
632	58985
633	56149
634	60130
635	64455
636	64449
637	58311
638	51308
639	54326
640	59227
641	60026
642	63548
643	67072
644	66256
645	68211
646	70577
647	72671
648	75124
649	73767
650	73742
651	75580
652	77427
653	76902
654	73620
655	79529
656	84966
657	82316
658	76099
659	75694
660	79361
661	84626
662	88758
663	87364
664	86213
665	90294
666	94898
667	91872
668	88104
669	88039
670	96814
671	104101
672	101960
673	103597
674	102584
675	102056
676	101998
677	100381
678	100500
679	102506
680	102627
681	99387
682	97749
683	107301
684	108246
685	107830
686	112305
687	112892
688	112000
689	111969
690	112238
691	115086
692	116631
693	113513
694	113626
695	112278
696	116668
697	126591
698	128023
699	124681
700	126899
701	124452
702	121572
703	128015
704	130456
705	131343
706	131414
707	127096
708	132888
709	132216
710	122118
711	122126
712	127998
713	129420
714	130145
715	134289
716	143489
717	144102
718	134969
719	131604
720	140207
721	144754
722	137928
723	137446
724	142577
725	138854
726	134895
727	131192
728	124857
729	113974
730	111516
731	120229
732	122126
733	116514
734	103526
735	93717
736	96014
737	108426
738	109368
739	97162
740	96104
741	98340
742	102290
743	96784
744	87913
745	80741
746	77402
747	81377
748	87516
749	85993
750	79328
751	74179
752	74124
753	70117
754	70470
755	73675
756	74093
757	74157
758	75795
759	75645
760	70166
761	69848
762	72749
763	72492
764	69385
765	69813
766	68831
767	68316
768	68161
769	68028
770	70440
771	71692
772	74207
773	73868
774	69670
775	68317
776	62843
777	58277
778	58130
779	63405
780	66897
781	72636
782	68575
783	61931
784	63440
785	64206
786	63647
787	65580
788	67653
789	67388
790	61717
791	60499
792	64194
793	66786
794	63330
795	62825
796	61044
797	59507
798	58020
799	56421
800	54304
801	52327
802	55670
803	61376
804	55632
805	49132
806	48309
807	50248
808	60052
809	67288
810	69102
811	67155
812	62178
813	64091
814	66421
815	66664
816	62282
817	64588
818	62728
819	60324
820	58991
821	55312
822	58480
823	62600
824	61432
825	62542
826	62832
827	60335
828	58476
829	55739
830	48387
831	44027
832	42327
833	44206
834	46459
835	48352
836	51098
837	51140
838	48631
839	42377
840	40494
841	44346
842	49916
843	48846
844	45770
845	47188
846	46641
847	42844
848	39790
849	39491
850	40075
851	38542
852	42480
853	41550
854	39028
855	43244
856	48266
857	44905
858	41409
859	41011
860	43192
861	44794
862	44746
863	42128
864	37651
865	40029
866	42333
867	38813
868	43245
869	46010
870	42023
871	37308
872	38155
873	36911
874	37084
875	38784
876	38671
877	41235
878	41147
879	35682
880	33495
881	33711
882	31273
883	29628
884	33212
885	33974
886	30223
887	31383
888	34552
889	39058
890	41125
891	40745
892	36282
893	32384
894	32736
895	32826
896	30233
897	29273
898	32590
899	36874
900	42502
901	40940
902	40050
903	40183
904	38900
905	40124
906	42914
907	42940
908	40439
909	35094
910	39380
911	44675
912	43853
913	44524
914	45651
915	47976
916	52583
917	48745
918	43558
919	45953
920	45839
921	40156
922	41168
923	41271
924	39891
925	37826
926	37531
927	41207
928	38769
929	35820
930	35975
931	34447
932	38054
933	35889
934	38444
935	41871
936	40849
937	40798
938	41428
939	41466
940	35369
941	31518
942	31730
943	36744
944	35342
945	30012
946	28538
947	29119
948	30991
949	38202
950	38341
951	34464
952	35640
953	39249
954	41251
955	43001
956	40421
957	42539
958	44462
959	39282
960	34200
961	32871
962	35753
963	35828
964	38370
965	33201
966	29470
967	30952
968	31102
969	31324
970	33996
971	33067
972	28901
973	30424
974	35324
975	34923
976	30877
977	29888
978	27505
979	30451
980	35158
981	31360
982	29364
983	32718
984	37799
985	36854
986	33413
987	32382
988	30862
989	32499
990	34444
991	32144
992	29611
993	28651
994	31194
995	38273
996	39718
997	35956
998	31033
999	26024
1000	26303
1001	27526
1002	30855
1003	32491
1004	26031
1005	24145
1006	24740
1007	26296
1008	25810
1009	22743
1010	19161
1011	17183
1012	20185
1013	20843
1014	24161
1015	25548
1016	30836
1017	33897
1018	31102
1019	29723
1020	29936
1021	28785
1022	31589
1023	33334
1024	33113