1	31697
2	31701
3	30766
4	29702
5	30031
6	30611
7	30987
8	29370
9	28372
10	27720
11	29200
12	31116
13	32510
14	32137
15	30273
16	28167
17	26927
18	27525
19	29396
20	31954
21	33441
22	34183
23	34325
24	34587
25	34430
26	33782
27	32566
28	31845
29	30674
30	31222
31	32075
32	33622
33	35564
34	37176
35	37771
36	37293
37	36591
38	36336
39	38616
40	41439
41	44379
42	45625
43	44528
44	42941
45	42571
46	41962
47	42836
48	44697
49	44610
50	43875
51	42824
52	42852
53	44081
54	45839
55	47102
56	47085
57	47420
58	46908
59	46473
60	47952
61	50384
62	53098
63	55662
64	56119
65	54651
66	53633
67	52870
68	52735
69	53756
70	55634
71	57189
72	57089
73	55407
74	54119
75	53699
76	54583
77	56328
78	57452
79	58371
80	59048
81	59407
82	59863
83	60665
84	61228
85	62643
86	64530
87	64927
88	64778
89	64501
90	65029
91	64834
92	63782
93	61916
94	61184
95	61852
96	62824
97	63311
98	62686
99	61499
100	61091
101	60717
102	61719
103	61672
104	60763
105	61039
106	62749
107	64137
108	62397
109	58134
110	55640
111	55568
112	58086
113	60598
114	61685
115	61509
116	59409
117	57186
118	54274
119	52252
120	51823
121	53156
122	54757
123	55462
124	55088
125	55753
126	55241
127	54503
128	53992
129	53710
130	53938
131	54503
132	53254
133	51159
134	48565
135	46983
136	45420
137	44815
138	44002
139	42776
140	41952
141	41012
142	40142
143	39433
144	38774
145	39203
146	40117
147	41512
148	43263
149	42623
150	41208
151	40251
152	41485
153	43118
154	43696
155	41392
156	38875
157	37078
158	36649
159	36471
160	36524
161	36853
162	37148
163	36807
164	37101
165	36565
166	36589
167	36526
168	37170
169	37962
170	38025
171	37480
172	36238
173	35155
174	34315
175	34210
176	34276
177	34253
178	34028
179	33444
180	33214
181	32443
182	31125
183	30287
184	30515
185	31173
186	31366
187	30560
188	29690
189	28754
190	27732
191	27688
192	27751
193	28582
194	29791
195	30669
196	30917
197	31371
198	30375
199	29956
200	29223
201	28921
202	27914
203	27033
204	27232
205	28554
206	29340
207	29398
208	27734
209	26499
210	26149
211	26451
212	26523
213	26115
214	25838
215	26512
216	26941
217	27648
218	28008
219	28590
220	28854
221	29686
222	29580
223	30052
224	29497
225	29110
226	27583
227	26395
228	25074
229	24736
230	25014
231	25591
232	25163
233	24294
234	24449
235	25220
236	26022
237	27928
238	28983
239	28020
240	26056
241	24128
242	23070
243	23635
244	24600
245	25838
246	27419
247	28235
248	28288
249	27697
250	27342
251	26926
252	26005
253	24854
254	23788
255	22679
256	21823
257	21951
258	23120
259	23972
260	22677
261	21848
262	22349
263	23696
264	24623
265	24801
266	24809
267	24896
268	25538
269	26028
270	26092
271	25718
272	25518
273	25551
274	25734
275	26728
276	27409
277	27839
278	27846
279	27320
280	26465
281	25416
282	25059
283	24712
284	25635
285	26480
286	26244
287	26004
288	26356
289	26369
290	25393
291	24827
292	23781
293	22441
294	21682
295	22227
296	23741
297	24685
298	24593
299	23627
300	22534
301	22301
302	22737
303	23788
304	25115
305	26192
306	26709
307	26297
308	26190
309	26973
310	27524
311	25734
312	23366
313	22558
314	22609
315	23033
316	23149
317	23358
318	23071
319	23013
320	22856
321	23204
322	24264
323	24539
324	24958
325	25784
326	26247
327	25365
328	22747
329	20840
330	20351
331	21746
332	24302
333	26189
334	26158
335	26366
336	26483
337	25697
338	24470
339	24229
340	25380
341	26222
342	25703
343	24491
344	23546
345	23924
346	25213
347	25259
348	23940
349	22573
350	21943
351	21777
352	21493
353	21497
354	22408
355	23212
356	24095
357	24025
358	23797
359	22907
360	21991
361	20669
362	20538
363	21218
364	22855
365	24516
366	25389
367	24423
368	22560
369	21453
370	21141
371	21783
372	22622
373	24446
374	25055
375	24350
376	23595
377	22800
378	22172
379	21083
380	20839
381	21089
382	21554
383	21867
384	21818
385	22438
386	23249
387	24211
388	24381
389	22918
390	21608
391	21970
392	22728
393	22587
394	21929
395	22524
396	23609
397	23709
398	23703
399	23442
400	22864
401	22400
402	21908
403	21373
404	21065
405	20938
406	21893
407	22590
408	24044
409	24852
410	25368
411	25021
412	24514
413	23831
414	23351
415	23732
416	24102
417	24128
418	24192
419	24381
420	25441
421	25898
422	25483
423	24865
424	23799
425	22639
426	22022
427	21913
428	22131
429	21485
430	21056
431	20668
432	19728
433	19169
434	19270
435	18861
436	19229
437	21299
438	23811
439	24763
440	24002
441	22939
442	21771
443	22444
444	22668
445	21739
446	21112
447	21102
448	21246
449	20852
450	20771
451	20552
452	19882
453	19179
454	20010
455	22000
456	22924
457	22611
458	22208
459	21738
460	21811
461	21656
462	20595
463	19797
464	19644
465	20387
466	21286
467	22260
468	23052
469	24740
470	24742
471	23948
472	23044
473	22823
474	22717
475	21915
476	21097
477	22131
478	22252
479	21093
480	20620
481	21268
482	20925
483	20407
484	20849
485	21888
486	22928
487	22744
488	21600
489	21081
490	22158
491	23718
492	24044
493	23726
494	22112
495	20865
496	19870
497	19484
498	20826
499	22496
500	24334
501	23557
502	22098
503	23677
504	25191
505	25137
506	23630
507	23107
508	23265
509	22539
510	21489
511	21103
512	22712
513	23907
514	22949
515	21680
516	21651
517	22370
518	22825
519	22477
520	22783
521	21447
522	20127
523	19844
524	21355
525	22114
526	21897
527	21353
528	20572
529	20956
530	21747
531	22055
532	21895
533	22580
534	22770
535	23236
536	23418
537	23341
538	24005
539	23810
540	22315
541	21514
542	21956
543	22138
544	22056
545	22775
546	22783
547	22525
548	22466
549	23116
550	23095
551	21770
552	21772
553	22356
554	22835
555	22888
556	22698
557	23876
558	24969
559	25834
560	24594
561	22768
562	22278
563	21856
564	22929
565	23978
566	24064
567	23312
568	23240
569	23051
570	23380
571	23402
572	24717
573	24640
574	23670
575	22362
576	21074
577	21034
578	22622
579	22535
580	22594
581	23595
582	23467
583	22454
584	22359
585	22463
586	21888
587	21216
588	21065
589	21069
590	21679
591	21755
592	21288
593	21475
594	22706
595	22148
596	21378
597	21284
598	22561
599	22793
600	22572
601	23107
602	23150
603	23077
604	23093
605	22703
606	23016
607	23189
608	23469
609	23533
610	24028
611	23789
612	22337
613	22346
614	23107
615	22470
616	21147
617	20542
618	20562
619	20911
620	21241
621	21097
622	20489
623	19996
624	21000
625	23139
626	23555
627	22097
628	21026
629	20158
630	20170
631	20645
632	20842
633	21358
634	20860
635	20815
636	22659
637	24223
638	24099
639	24158
640	24112
641	23848
642	21828
643	21162
644	20136
645	18909
646	19041
647	19216
648	19147
649	19006
650	19080
651	18421
652	17363
653	16365
654	17253
655	19974
656	20969
657	22268
658	22280
659	20069
660	20480
661	21808
662	22440
663	23399
664	23841
665	23122
666	20626
667	19387
668	20124
669	20900
670	20606
671	19028
672	17411
673	16989
674	17562
675	17976
676	19691
677	20699
678	19510
679	17863
680	17691
681	17963
682	18761
683	19713
684	19832
685	20925
686	20486
687	19537
688	19102
689	18121
690	17022
691	17420
692	18760
693	19711
694	21145
695	21689
696	22337
697	23392
698	21594
699	19625
700	18889
701	20502
702	22398
703	22276
704	22418
705	25630
706	27319
707	24160
708	20689
709	19880
710	19830
711	20971
712	23302
713	23157
714	21087
715	18044
716	16875
717	18340
718	19364
719	18518
720	17001
721	16657
722	17274
723	18163
724	19812
725	20965
726	19484
727	17783
728	18772
729	20159
730	21484
731	23083
732	22433
733	20741
734	19360
735	19186
736	20161
737	19988
738	20197
739	19567
740	18930
741	18575
742	19135
743	18807
744	18303
745	20798
746	22045
747	20407
748	19999
749	19766
750	19605
751	20982
752	22393
753	20737
754	18864
755	19876
756	19073
757	18242
758	17147
759	15854
760	14918
761	16635
762	19812
763	22769
764	21627
765	20955
766	19466
767	18101
768	16246
769	17382
770	19938
771	20206
772	20292
773	22897
774	22440
775	20211
776	20204
777	20594
778	19327
779	18997
780	20159
781	20824
782	20913
783	19381
784	18183
785	16438
786	17321
787	18666
788	18098
789	18732
790	18950
791	18806
792	18280
793	19170
794	19000
795	17206
796	15966
797	17352
798	20377
799	21449
800	21541
801	19923
802	19070
803	20529
804	20214
805	18859
806	18475
807	18744
808	18571
809	19581
810	19558
811	20457
812	22671
813	21606
814	20747
815	20818
816	19962
817	19730
818	20091
819	19794
820	18601
821	19593
822	19693
823	20925
824	21578
825	19797
826	18307
827	17838
828	18859
829	20452
830	18711
831	18746
832	19118
833	19272
834	18535
835	18046
836	18288
837	18796
838	19831
839	18647
840	18334
841	20366
842	20391
843	17436
844	15875
845	16908
846	18216
847	18782
848	18037
849	16900
850	16672
851	16368
852	16427
853	15926
854	16613
855	17229
856	18700
857	18014
858	16907
859	17118
860	17143
861	19233
862	20668
863	18661
864	18134
865	19647
866	20329
867	18346
868	18680
869	19792
870	20486
871	18422
872	17703
873	16994
874	17186
875	19348
876	20291
877	19882
878	20421
879	21553
880	22533
881	21645
882	20128
883	20197
884	20857
885	22074
886	23072
887	20984
888	20461
889	19555
890	19207
891	20161
892	20204
893	19824
894	20025
895	19252
896	18228
897	18079
898	17703
899	17357
900	16965
901	18443
902	18504
903	21077
904	21669
905	18233
906	16572
907	18871
908	20387
909	20441
910	20753
911	21062
912	20458
913	19222
914	22744
915	21481
916	20733
917	21198
918	20479
919	20827
920	20246
921	18683
922	18561
923	19232
924	18965
925	17527
926	17624
927	19643
928	19303
929	17111
930	18221
931	21183
932	18906
933	19386
934	19512
935	18046
936	16554
937	16800
938	19049
939	18891
940	19641
941	21093
942	22200
943	19456
944	15390
945	14106
946	14367
947	17332
948	19282
949	17458
950	17232
951	17851
952	16638
953	16608
954	16955
955	18784
956	21811
957	21428
958	19346
959	17892
960	18212
961	18958
962	20997
963	20590
964	19339
965	18820
966	18833
967	20682
968	22525
969	21212
970	20665
971	18851
972	17827
973	17571
974	17167
975	18290
976	20784
977	20314
978	22236
979	22458
980	20232
981	17849
982	16653
983	18420
984	20054
985	18501
986	18630
987	21357
988	21311
989	18956
990	16680
991	16016
992	16494
993	18693
994	17458
995	17018
996	18171
997	18696
998	18957
999	19245
1000	19841
1001	18047
1002	17379
1003	14980
1004	15338
1005	15242
1006	15302
1007	18403
1008	20741
1009	19699
1010	19984
1011	20841
1012	21162
1013	20543
1014	19399
1015	20573
1016	19473
1017	15604
1018	17495
1019	19407
1020	20639
1021	19162
1022	18937
1023	15828
1024	16774