1	11902
2	11121
3	9863
4	8464
5	7521
6	7192
7	6789
8	6409
9	6138
10	6826
11	8596
12	10863
13	13164
14	14148
15	14469
16	14425
17	13027
18	11024
19	9090
20	7729
21	7255
22	7572
23	7909
24	8532
25	9200
26	9469
27	9205
28	8768
29	8142
30	8731
31	9785
32	11133
33	12446
34	13368
35	14728
36	15293
37	15148
38	13952
39	12778
40	11697
41	11378
42	11399
43	11459
44	11482
45	11300
46	10388
47	9718
48	9710
49	10418
50	11619
51	12186
52	12310
53	11727
54	10930
55	10639
56	10363
57	10812
58	11113
59	11800
60	12598
61	13599
62	14018
63	14546
64	15545
65	16532
66	16681
67	15526
68	13759
69	12249
70	11743
71	11942
72	12277
73	12897
74	13806
75	14502
76	14296
77	13616
78	12978
79	13453
80	14881
81	16616
82	17503
83	17057
84	16418
85	16164
86	16828
87	17107
88	16468
89	15044
90	15117
91	16152
92	17863
93	19511
94	19766
95	19216
96	19496
97	20245
98	21326
99	22235
100	22196
101	22003
102	22785
103	24269
104	25193
105	25531
106	24709
107	23349
108	22438
109	22651
110	25410
111	28384
112	30892
113	30532
114	29241
115	28982
116	29353
117	30671
118	32149
119	33143
120	34396
121	36410
122	36695
123	36781
124	37669
125	39614
126	41944
127	41992
128	40479
129	38389
130	37153
131	37580
132	37800
133	38227
134	37752
135	38488
136	38073
137	38192
138	36154
139	33907
140	32758
141	32495
142	33206
143	34163
144	34309
145	33060
146	31522
147	29032
148	28037
149	27218
150	26434
151	25288
152	24404
153	23071
154	21739
155	21048
156	21479
157	21635
158	22023
159	22405
160	22624
161	21363
162	20187
163	18278
164	18452
165	18292
166	17934
167	17017
168	16099
169	15565
170	15714
171	16045
172	15463
173	14523
174	13869
175	13720
176	13889
177	13945
178	14134
179	14528
180	15166
181	15950
182	16424
183	16499
184	16129
185	16090
186	15790
187	15148
188	14644
189	14982
190	15918
191	16778
192	16473
193	14911
194	13370
195	13238
196	14725
197	16396
198	16961
199	16167
200	14698
201	13883
202	14280
203	14884
204	14631
205	14034
206	12992
207	11972
208	11036
209	11097
210	11784
211	12213
212	12281
213	12699
214	13364
215	13414
216	12868
217	12376
218	12517
219	12988
220	12610
221	12282
222	11870
223	11934
224	12206
225	12879
226	13023
227	12661
228	12557
229	12487
230	12554
231	12264
232	12310
233	12384
234	12821
235	13199
236	13191
237	13380
238	14264
239	14231
240	14186
241	14123
242	13722
243	12816
244	10575
245	10301
246	10584
247	10986
248	11053
249	11812
250	13492
251	14802
252	15035
253	14444
254	13385
255	12326
256	11663
257	12481
258	13445
259	13639
260	13199
261	12172
262	10809
263	9549
264	9626
265	10459
266	11388
267	12044
268	13327
269	14330
270	14769
271	14417
272	14347
273	14903
274	15467
275	14872
276	13337
277	11963
278	12756
279	14801
280	15815
281	15481
282	14961
283	15008
284	15289
285	15590
286	14994
287	15817
288	16846
289	16920
290	16031
291	14761
292	14186
293	13931
294	14858
295	15746
296	16409
297	16599
298	16799
299	16267
300	15086
301	15187
302	15975
303	18266
304	19626
305	19231
306	18222
307	17634
308	18006
309	20119
310	23113
311	23548
312	21658
313	19833
314	18793
315	18501
316	19436
317	21343
318	23579
319	25631
320	26922
321	26551
322	25416
323	23870
324	22253
325	21313
326	20437
327	20012
328	20633
329	22321
330	23683
331	23418
332	23306
333	23292
334	21846
335	20341
336	19687
337	21219
338	23695
339	24899
340	24800
341	24891
342	23989
343	22953
344	21817
345	21246
346	23019
347	25988
348	27931
349	26202
350	23592
351	23748
352	25769
353	25499
354	23939
355	23541
356	23899
357	24144
358	23438
359	22648
360	23111
361	23919
362	23278
363	22342
364	23091
365	24642
366	26167
367	26154
368	24489
369	23406
370	23675
371	23366
372	22839
373	22468
374	22663
375	23144
376	24630
377	25081
378	24122
379	22182
380	21796
381	21719
382	21447
383	20901
384	20716
385	20053
386	19896
387	20551
388	22108
389	23845
390	25489
391	25751
392	24761
393	23482
394	23588
395	25418
396	27373
397	27255
398	27404
399	27451
400	27633
401	27349
402	27577
403	29793
404	32071
405	33712
406	32223
407	26663
408	22543
409	22070
410	23826
411	24231
412	25293
413	27030
414	29510
415	31388
416	31536
417	30818
418	31256
419	33779
420	37167
421	39027
422	38063
423	35733
424	34662
425	34193
426	33233
427	33850
428	35405
429	35184
430	34409
431	33172
432	34059
433	36404
434	38763
435	39329
436	39814
437	39795
438	39065
439	38765
440	39737
441	42025
442	42660
443	42216
444	41364
445	39966
446	40273
447	41264
448	42030
449	39665
450	39478
451	41032
452	42432
453	44073
454	45808
455	45145
456	42754
457	41060
458	40899
459	43205
460	47303
461	49160
462	50177
463	52796
464	54486
465	54051
466	55496
467	55847
468	56620
469	60537
470	61439
471	60320
472	57513
473	62849
474	72066
475	79419
476	80516
477	78875
478	75764
479	74770
480	77705
481	84846
482	93685
483	96465
484	91543
485	83369
486	81466
487	82832
488	84426
489	87033
490	90275
491	95752
492	99431
493	103774
494	102031
495	100060
496	99555
497	98399
498	97698
499	96714
500	97818
501	98833
502	97197
503	96396
504	99844
505	108135
506	118353
507	122749
508	122152
509	121453
510	122163
511	122552
512	124481
513	127484
514	127736
515	127514
516	131755
517	139646
518	147836
519	148108
520	148432
521	148213
522	149974
523	157581
524	168383
525	171824
526	173562
527	174096
528	171986
529	171654
530	173395
531	180837
532	187945
533	187511
534	186939
535	199017
536	214043
537	215689
538	211364
539	208793
540	214293
541	221501
542	217002
543	210171
544	210090
545	213831
546	211229
547	206838
548	202788
549	206402
550	220889
551	234521
552	230582
553	223067
554	224499
555	224026
556	219290
557	215557
558	205460
559	199857
560	204296
561	210832
562	218030
563	217407
564	221548
565	221947
566	215734
567	206421
568	201119
569	199467
570	205421
571	216211
572	228423
573	231160
574	224621
575	223959
576	224517
577	228643
578	228947
579	222035
580	213776
581	209293
582	211050
583	216271
584	223248
585	227468
586	222823
587	216889
588	207598
589	198104
590	195362
591	198954
592	198329
593	192077
594	182375
595	176191
596	177171
597	171376
598	162899
599	156543
600	151679
601	145974
602	145764
603	152637
604	155649
605	153808
606	142976
607	135207
608	134938
609	132953
610	128852
611	128433
612	126318
613	124261
614	120462
615	114401
616	107104
617	105240
618	99870
619	95764
620	95374
621	94843
622	89689
623	84827
624	79486
625	80422
626	86330
627	84579
628	81047
629	76951
630	76184
631	75184
632	69707
633	66342
634	66910
635	72832
636	78623
637	78361
638	71730
639	66650
640	62264
641	62799
642	66053
643	67030
644	63979
645	64171
646	67517
647	68460
648	69250
649	69860
650	68178
651	63990
652	66250
653	70937
654	73315
655	69197
656	60724
657	57115
658	56526
659	60442
660	65690
661	63321
662	57511
663	58801
664	61906
665	62177
666	58673
667	54831
668	55461
669	58549
670	59414
671	60607
672	61000
673	61670
674	62414
675	55222
676	47696
677	45571
678	48852
679	50844
680	49333
681	47455
682	50029
683	49940
684	43056
685	40361
686	38799
687	37446
688	38388
689	39707
690	43120
691	45608
692	43455
693	38659
694	37553
695	40851
696	39827
697	36429
698	35405
699	34378
700	33565
701	30427
702	29625
703	34028
704	36814
705	37724
706	36111
707	33062
708	32071
709	33366
710	34324
711	31047
712	28319
713	27676
714	26926
715	27160
716	28569
717	31100
718	29591
719	26973
720	26402
721	27840
722	29305
723	29866
724	28970
725	26683
726	29087
727	29272
728	24636
729	22373
730	23728
731	26236
732	26459
733	23336
734	20819
735	22681
736	26948
737	32014
738	32595
739	27576
740	25245
741	27683
742	28190
743	27213
744	28084
745	27192
746	22460
747	19428
748	17583
749	17892
750	19845
751	21781
752	21805
753	20180
754	19907
755	18610
756	19262
757	20284
758	18753
759	18956
760	17364
761	17507
762	16728
763	13579
764	13702
765	15993
766	14905
767	13838
768	13450
769	12491
770	14352
771	15065
772	15173
773	15804
774	14766
775	14336
776	12977
777	12543
778	13359
779	12824
780	13710
781	14489
782	15696
783	16647
784	16509
785	16749
786	16629
787	17430
788	17646
789	16886
790	14078
791	12124
792	12273
793	14088
794	15224
795	13751
796	12086
797	11277
798	12792
799	13311
800	11022
801	11319
802	14187
803	14611
804	12959
805	10900
806	9218
807	9810
808	10261
809	10237
810	12061
811	13540
812	15462
813	12897
814	12108
815	13834
816	10756
817	10964
818	11618
819	10310
820	11244
821	12102
822	12192
823	14196
824	14946
825	11727
826	9967
827	12138
828	13054
829	15146
830	13242
831	11900
832	12829
833	10650
834	9995
835	12848
836	14867
837	14093
838	16359
839	18549
840	16547
841	14398
842	15333
843	11547
844	7526
845	7192
846	7537
847	7409
848	6998
849	8340
850	9794
851	11124
852	11173
853	10271
854	8092
855	6519
856	6685
857	8599
858	10607
859	9511
860	7357
861	7342
862	8505
863	8785
864	11058
865	11190
866	10248
867	10082
868	10083
869	9416
870	9036
871	9126
872	10360
873	11414
874	9887
875	8967
876	9571
877	10376
878	9175
879	7572
880	5105
881	5176
882	8379
883	9366
884	11264
885	13705
886	13367
887	9393
888	8420
889	8091
890	6826
891	6968
892	8368
893	8034
894	7386
895	7254
896	8424
897	9817
898	7919
899	6893
900	6862
901	6266
902	6667
903	7075
904	8536
905	8959
906	8516
907	10341
908	12145
909	12406
910	11635
911	12083
912	15833
913	12867
914	10403
915	11251
916	10759
917	8338
918	8970
919	11342
920	11340
921	10781
922	8915
923	8559
924	10915
925	12656
926	14085
927	11211
928	8387
929	6404
930	7727
931	10312
932	7739
933	6712
934	6576
935	7404
936	8895
937	7093
938	5511
939	7991
940	8276
941	8362
942	11367
943	10058
944	9657
945	9137
946	8053
947	8908
948	8883
949	11152
950	12473
951	9469
952	7675
953	9357
954	8828
955	8627
956	8075
957	7275
958	8331
959	11604
960	11095
961	9991
962	7680
963	7212
964	7956
965	8168
966	8036
967	7170
968	6263
969	7191
970	9679
971	12577
972	10598
973	7573
974	7441
975	8580
976	10666
977	8781
978	7181
979	7979
980	8181
981	8560
982	8178
983	8283
984	8819
985	10858
986	11045
987	9413
988	7292
989	7392
990	11114
991	13353
992	12552
993	8330
994	7419
995	6361
996	7624
997	7513
998	7013
999	6010
1000	6882
1001	8147
1002	10692
1003	8737
1004	8644
1005	8482
1006	8087
1007	8440
1008	8537
1009	7405
1010	6716
1011	5984
1012	6959
1013	6489
1014	7315
1015	7141
1016	6400
1017	5180
1018	5042
1019	5415
1020	4862
1021	6194
1022	8502
1023	7857
1024	4855