1	21146
2	21263
3	21995
4	22390
5	22400
6	22003
7	21679
8	21166
9	21036
10	20949
11	21070
12	21487
13	21962
14	22437
15	22812
16	23033
17	23096
18	23314
19	23040
20	22889
21	22282
22	21865
23	22310
24	22788
25	22811
26	22921
27	22775
28	23031
29	23219
30	24159
31	23997
32	24014
33	23590
34	23610
35	23155
36	22970
37	22180
38	21723
39	22168
40	22978
41	23521
42	24330
43	24564
44	24869
45	26180
46	26200
47	26429
48	26970
49	26917
50	26378
51	25963
52	25572
53	25536
54	25222
55	25222
56	25371
57	25647
58	25952
59	26588
60	27555
61	27907
62	27658
63	27499
64	27542
65	27716
66	28427
67	29080
68	29769
69	29777
70	29701
71	30191
72	30082
73	30201
74	30541
75	31351
76	31431
77	31462
78	31776
79	33123
80	34469
81	35549
82	36962
83	38115
84	38112
85	37532
86	37572
87	38295
88	39265
89	40663
90	42241
91	42936
92	43637
93	43891
94	43963
95	44484
96	44268
97	43872
98	43708
99	43451
100	43393
101	42195
102	42038
103	41900
104	40557
105	39878
106	38794
107	37969
108	37542
109	36265
110	35376
111	34201
112	33534
113	32211
114	30305
115	29665
116	28953
117	28267
118	27939
119	27663
120	27955
121	28839
122	29052
123	28597
124	28193
125	27879
126	27659
127	27156
128	26095
129	25206
130	25124
131	25659
132	25618
133	25300
134	24602
135	24711
136	24753
137	24974
138	25693
139	25762
140	26625
141	26949
142	27010
143	25987
144	25572
145	25760
146	26356
147	26761
148	28137
149	28079
150	27970
151	28379
152	29017
153	29748
154	30653
155	30727
156	30999
157	31163
158	30266
159	29513
160	28449
161	28117
162	28601
163	28276
164	28572
165	27888
166	28172
167	28681
168	29436
169	30752
170	30932
171	30409
172	29719
173	29022
174	29039
175	29366
176	29710
177	29799
178	30280
179	30309
180	30099
181	29309
182	28350
183	26964
184	26563
185	26562
186	26559
187	26942
188	27653
189	27961
190	27285
191	27153
192	27376
193	28210
194	28535
195	29286
196	28800
197	28610
198	27712
199	26840
200	26235
201	25681
202	25938
203	27018
204	27734
205	28904
206	29372
207	30709
208	31037
209	30011
210	28908
211	28617
212	29373
213	29591
214	29822
215	29886
216	30499
217	31328
218	31250
219	31398
220	31433
221	32085
222	33781
223	35477
224	36831
225	37522
226	37394
227	37399
228	37910
229	38357
230	39364
231	41213
232	41868
233	42543
234	42368
235	42489
236	42121
237	40934
238	40692
239	39979
240	40250
241	40122
242	39774
243	39145
244	38165
245	37657
246	38129
247	39691
248	40338
249	40126
250	40516
251	40477
252	41060
253	41618
254	42128
255	42699
256	44103
257	45153
258	46678
259	48855
260	50516
261	52097
262	53685
263	54330
264	55716
265	57824
266	61284
267	63503
268	66702
269	68356
270	68955
271	68725
272	68399
273	68823
274	67858
275	66793
276	64010
277	61238
278	59501
279	57533
280	54837
281	51297
282	49941
283	48847
284	47246
285	45494
286	43794
287	41988
288	40153
289	38999
290	38310
291	38610
292	38570
293	39466
294	41191
295	43634
296	46572
297	50094
298	54559
299	58773
300	62216
301	65234
302	68299
303	70801
304	71030
305	70114
306	66933
307	64159
308	60330
309	57970
310	56626
311	53733
312	52327
313	51998
314	53420
315	54495
316	55151
317	54996
318	55278
319	56253
320	57361
321	58773
322	61134
323	63363
324	65641
325	67428
326	68157
327	70259
328	74333
329	80495
330	88204
331	93888
332	98276
333	102966
334	107432
335	113070
336	118652
337	123100
338	127408
339	131862
340	134368
341	136278
342	135905
343	133811
344	131905
345	128836
346	125540
347	123115
348	120842
349	119525
350	115884
351	112815
352	110514
353	108498
354	106654
355	103000
356	101699
357	100268
358	99033
359	95557
360	92953
361	88685
362	82681
363	77323
364	74562
365	72137
366	70474
367	68107
368	65785
369	62907
370	60175
371	57713
372	56217
373	56069
374	55547
375	54530
376	51634
377	49840
378	49167
379	46808
380	45085
381	43898
382	43382
383	42913
384	42756
385	43104
386	43557
387	44145
388	44458
389	45030
390	44525
391	44453
392	45085
393	46675
394	46787
395	46810
396	46634
397	46306
398	46775
399	46466
400	47040
401	47972
402	48727
403	48324
404	48046
405	49368
406	51898
407	52307
408	51724
409	48707
410	46046
411	44545
412	45660
413	47553
414	48662
415	48468
416	47461
417	45910
418	44882
419	44334
420	44461
421	44523
422	44854
423	44769
424	44340
425	44754
426	45407
427	45345
428	44415
429	44262
430	45182
431	46037
432	45907
433	45313
434	43911
435	42897
436	41759
437	41953
438	43172
439	44432
440	44637
441	43348
442	41847
443	41269
444	41050
445	41098
446	41639
447	42817
448	45173
449	47541
450	48479
451	47366
452	47528
453	47461
454	48181
455	49590
456	51276
457	54251
458	57594
459	60119
460	60854
461	61219
462	62800
463	65812
464	69204
465	72208
466	75442
467	77900
468	79969
469	84303
470	85556
471	88036
472	89953
473	97689
474	102497
475	107046
476	109738
477	111061
478	110380
479	109773
480	108948
481	107911
482	106412
483	104082
484	100918
485	96152
486	90303
487	86647
488	83666
489	79196
490	72958
491	68228
492	65060
493	64134
494	61924
495	57874
496	54164
497	50898
498	50833
499	50464
500	49162
501	47223
502	46470
503	47004
504	46212
505	45417
506	44994
507	44643
508	45261
509	46683
510	48528
511	48640
512	49471
513	50658
514	49735
515	48317
516	46017
517	44691
518	44675
519	44447
520	42813
521	39974
522	39794
523	40536
524	42530
525	43777
526	42919
527	41622
528	40914
529	40524
530	39545
531	38096
532	37298
533	36797
534	35746
535	35183
536	36160
537	36422
538	36408
539	36439
540	37004
541	36464
542	36254
543	36823
544	39049
545	40319
546	38906
547	37151
548	35945
549	34764
550	34542
551	35838
552	37350
553	37766
554	37523
555	37530
556	38406
557	39619
558	39431
559	37961
560	37957
561	37767
562	38275
563	38063
564	39261
565	40490
566	40951
567	40675
568	42025
569	43841
570	44617
571	44758
572	44919
573	44703
574	44204
575	44568
576	45314
577	46553
578	47436
579	47168
580	46768
581	47992
582	49821
583	50901
584	50647
585	49987
586	49080
587	49201
588	49887
589	52147
590	53999
591	54724
592	55524
593	55521
594	55427
595	55839
596	58240
597	58188
598	58385
599	58506
600	58785
601	59458
602	59394
603	59999
604	59790
605	61206
606	62715
607	61318
608	59517
609	59487
610	60100
611	60426
612	60789
613	64871
614	67818
615	70710
616	68556
617	67706
618	68211
619	67508
620	65522
621	65774
622	66523
623	65235
624	62943
625	63335
626	65689
627	66512
628	66261
629	64762
630	65104
631	63815
632	62807
633	63855
634	64074
635	64359
636	63522
637	62797
638	63092
639	66495
640	68710
641	68919
642	69590
643	72117
644	69962
645	69717
646	72816
647	73887
648	74470
649	74377
650	74661
651	74128
652	74668
653	73582
654	73858
655	78918
656	81478
657	82899
658	81682
659	79965
660	80579
661	84425
662	88067
663	87020
664	84848
665	82171
666	82823
667	85334
668	87922
669	88703
670	86399
671	87344
672	89928
673	89319
674	88205
675	89202
676	92803
677	93793
678	92751
679	92992
680	94071
681	93929
682	95411
683	98462
684	97896
685	96792
686	95902
687	96080
688	98715
689	102296
690	105639
691	101985
692	100912
693	102504
694	102003
695	98803
696	99400
697	100833
698	99641
699	97349
700	96909
701	97612
702	98976
703	101467
704	102562
705	103078
706	104619
707	103921
708	103385
709	105409
710	104738
711	103280
712	104605
713	105142
714	104004
715	105332
716	106788
717	105482
718	104670
719	107635
720	108222
721	106457
722	107335
723	106955
724	104884
725	103234
726	105308
727	101706
728	98787
729	95495
730	96257
731	96293
732	93825
733	89604
734	87911
735	87952
736	86482
737	86782
738	87117
739	84572
740	82294
741	79163
742	79514
743	79116
744	79709
745	81545
746	80435
747	75398
748	71714
749	70560
750	70032
751	68172
752	68608
753	68916
754	68387
755	68701
756	68387
757	68915
758	66571
759	63846
760	61343
761	63531
762	64820
763	63314
764	63179
765	64448
766	65856
767	67898
768	67129
769	65354
770	64003
771	62136
772	62507
773	62869
774	60824
775	58516
776	58088
777	58367
778	58033
779	59521
780	59856
781	60018
782	60756
783	60976
784	59945
785	58029
786	56113
787	57884
788	58884
789	60770
790	59481
791	60067
792	60453
793	59238
794	55186
795	55319
796	58078
797	60282
798	59893
799	58283
800	56133
801	56549
802	55586
803	54561
804	55209
805	55702
806	54935
807	53838
808	54481
809	54176
810	52891
811	55901
812	58234
813	55640
814	52947
815	51956
816	52416
817	52018
818	50669
819	50359
820	50640
821	51556
822	52105
823	51696
824	49605
825	50466
826	51961
827	50540
828	48928
829	47388
830	46770
831	45505
832	45136
833	46276
834	49022
835	48443
836	46605
837	46741
838	46482
839	46092
840	46537
841	45999
842	46605
843	45279
844	42811
845	44137
846	46096
847	46458
848	45072
849	43037
850	41360
851	41563
852	42098
853	41677
854	40747
855	40301
856	38877
857	37829
858	37617
859	35999
860	36014
861	37365
862	38684
863	38069
864	37656
865	38557
866	39317
867	38265
868	38476
869	38454
870	38103
871	37998
872	38447
873	38364
874	38300
875	38037
876	37070
877	36758
878	36270
879	35306
880	34227
881	34211
882	34558
883	34399
884	34856
885	35494
886	35180
887	36210
888	37776
889	36355
890	35051
891	35230
892	34281
893	33849
894	35243
895	33686
896	32985
897	32986
898	33722
899	35379
900	35722
901	35155
902	34834
903	35282
904	37626
905	39842
906	40252
907	39549
908	40423
909	39276
910	38558
911	39798
912	41839
913	42971
914	42457
915	41623
916	41968
917	42332
918	42284
919	41803
920	40542
921	38822
922	38582
923	37316
924	35758
925	36174
926	34467
927	34772
928	33980
929	33788
930	35276
931	35289
932	35577
933	33690
934	31759
935	32275
936	34596
937	34918
938	34938
939	34275
940	32777
941	34238
942	35356
943	34929
944	35968
945	34979
946	31197
947	30214
948	32158
949	32322
950	32467
951	32611
952	31159
953	32085
954	32396
955	32618
956	33430
957	33408
958	32837
959	33362
960	34556
961	33073
962	33224
963	33866
964	33191
965	30722
966	29955
967	29270
968	28762
969	27264
970	27906
971	29075
972	29154
973	29928
974	31606
975	32976
976	32580
977	31931
978	31281
979	29595
980	30585
981	30268
982	30089
983	30611
984	31326
985	30863
986	27123
987	26336
988	28093
989	30236
990	29357
991	26936
992	27128
993	26676
994	27024
995	28904
996	29786
997	28422
998	29697
999	28805
1000	25112
1001	24779
1002	25893
1003	27155
1004	27115
1005	27362
1006	28971
1007	30296
1008	28749
1009	28117
1010	28115
1011	29073
1012	30148
1013	30091
1014	29815
1015	30353
1016	28932
1017	27248
1018	27274
1019	27856
1020	30166
1021	32020
1022	29568
1023	28029
1024	28003