1	16346
2	16774
3	16884
4	17132
5	17626
6	17235
7	16772
8	15655
9	14960
10	14242
11	14018
12	14891
13	16913
14	19008
15	19728
16	19205
17	17984
18	17278
19	16713
20	16107
21	15734
22	16247
23	16858
24	17831
25	18630
26	19605
27	20327
28	20309
29	19021
30	17173
31	15216
32	13856
33	13516
34	13770
35	14435
36	15885
37	16946
38	17513
39	17275
40	16584
41	15742
42	15964
43	15355
44	15814
45	16929
46	17090
47	17979
48	19316
49	21139
50	22337
51	22167
52	19905
53	17169
54	15140
55	14404
56	14701
57	15940
58	16826
59	17616
60	18297
61	17828
62	16637
63	14770
64	14391
65	15283
66	17256
67	18489
68	18442
69	17509
70	17393
71	19030
72	20144
73	20869
74	20609
75	19480
76	17480
77	16032
78	16200
79	17373
80	18512
81	19085
82	19634
83	21182
84	22665
85	23861
86	23983
87	24574
88	25459
89	25833
90	26298
91	26431
92	27040
93	27605
94	26532
95	24736
96	22375
97	20856
98	19748
99	19239
100	19415
101	19706
102	21342
103	23292
104	25280
105	26659
106	27760
107	28836
108	29393
109	29129
110	28663
111	27717
112	29097
113	31317
114	33731
115	35745
116	38321
117	41302
118	44525
119	47623
120	49346
121	52017
122	52963
123	53669
124	55963
125	60460
126	63498
127	63926
128	63255
129	63269
130	67599
131	74965
132	82418
133	85211
134	82569
135	78400
136	74551
137	74867
138	78069
139	83032
140	90657
141	93135
142	94617
143	94878
144	94947
145	94526
146	92439
147	89421
148	86208
149	79518
150	72610
151	69231
152	68676
153	64908
154	60092
155	56286
156	54709
157	53548
158	50867
159	47642
160	45515
161	44760
162	45934
163	47108
164	46724
165	43997
166	40555
167	37187
168	35701
169	34178
170	32461
171	31160
172	30460
173	29657
174	28888
175	28631
176	28587
177	28704
178	27607
179	25932
180	24608
181	24265
182	24511
183	24572
184	22888
185	20864
186	20467
187	21908
188	24239
189	25391
190	25178
191	24665
192	24779
193	25440
194	25664
195	25196
196	24213
197	24141
198	24461
199	24493
200	23873
201	23614
202	23219
203	23059
204	22583
205	21781
206	20043
207	20089
208	20898
209	21076
210	20569
211	19589
212	18786
213	17554
214	17048
215	17030
216	18274
217	20855
218	22877
219	23011
220	20230
221	17242
222	15361
223	16051
224	18130
225	20098
226	19937
227	18623
228	18175
229	18106
230	18399
231	19086
232	20426
233	21149
234	20336
235	18932
236	18884
237	21219
238	22695
239	21411
240	18236
241	16558
242	16581
243	17148
244	16898
245	16216
246	15507
247	14372
248	14465
249	16318
250	19390
251	22278
252	24052
253	23388
254	21598
255	21034
256	22170
257	23153
258	22771
259	21366
260	19549
261	18332
262	18616
263	19117
264	20420
265	20618
266	21065
267	21036
268	21049
269	22205
270	23171
271	23231
272	22167
273	20812
274	21247
275	22860
276	24043
277	24436
278	24402
279	24236
280	23869
281	23964
282	25122
283	26004
284	25280
285	23171
286	20857
287	20533
288	21415
289	22392
290	23700
291	25262
292	25999
293	24422
294	21528
295	19012
296	17916
297	17567
298	18437
299	19461
300	20121
301	21212
302	22290
303	22766
304	22792
305	24452
306	27755
307	29569
308	27518
309	24227
310	22373
311	22022
312	24038
313	25995
314	27152
315	27671
316	28998
317	29678
318	27925
319	26144
320	27239
321	31801
322	36773
323	38997
324	37684
325	34500
326	31679
327	31835
328	33996
329	36847
330	39352
331	40625
332	41100
333	41199
334	40176
335	40041
336	40343
337	42247
338	45605
339	48583
340	49476
341	49252
342	48629
343	45674
344	43750
345	45210
346	49069
347	53308
348	55400
349	55316
350	53244
351	51469
352	51347
353	48559
354	45583
355	45980
356	48451
357	48676
358	47372
359	46110
360	45952
361	44834
362	43504
363	43496
364	44340
365	44458
366	43988
367	45170
368	48811
369	51768
370	51394
371	48879
372	45298
373	42937
374	41128
375	41968
376	44054
377	44921
378	44226
379	42990
380	41139
381	39306
382	38831
383	38868
384	38324
385	38236
386	37637
387	36455
388	34150
389	33709
390	34353
391	35814
392	35718
393	36153
394	37403
395	41174
396	46381
397	45807
398	41542
399	37955
400	37577
401	37528
402	37443
403	37656
404	38602
405	40052
406	41753
407	40785
408	38239
409	35691
410	36262
411	38645
412	40237
413	40781
414	42692
415	44448
416	44834
417	43803
418	45974
419	47855
420	46053
421	42477
422	41988
423	44296
424	46116
425	48614
426	51286
427	51647
428	50948
429	51019
430	55372
431	57519
432	56718
433	54782
434	52290
435	52214
436	55290
437	61599
438	68438
439	68648
440	64503
441	60325
442	60009
443	62828
444	65673
445	69650
446	73469
447	74335
448	73749
449	70022
450	66518
451	62382
452	60207
453	58670
454	57926
455	57379
456	56855
457	55581
458	57106
459	59649
460	59725
461	56972
462	55238
463	56969
464	60595
465	63631
466	65386
467	67447
468	74550
469	79019
470	74986
471	72262
472	69303
473	70408
474	74967
475	81553
476	86459
477	90075
478	94306
479	98778
480	106439
481	113004
482	110319
483	104307
484	104576
485	108667
486	115439
487	124529
488	132569
489	134977
490	134745
491	140264
492	146035
493	153046
494	152842
495	154842
496	162312
497	166283
498	173716
499	180469
500	179837
501	174026
502	175943
503	182841
504	188173
505	190350
506	189062
507	182873
508	183646
509	190443
510	198806
511	199746
512	198116
513	198571
514	201123
515	205845
516	206832
517	208333
518	217478
519	225895
520	231314
521	231961
522	237901
523	242637
524	241555
525	238017
526	242245
527	251415
528	258882
529	256442
530	250866
531	253366
532	267354
533	282890
534	292942
535	305027
536	318911
537	324599
538	321998
539	316237
540	320664
541	349810
542	370298
543	370922
544	369377
545	384289
546	398703
547	396990
548	388849
549	388310
550	402984
551	422797
552	442024
553	461213
554	478274
555	489110
556	501170
557	522056
558	532148
559	533290
560	529017
561	515427
562	511492
563	507408
564	506392
565	491867
566	476124
567	475064
568	475275
569	470093
570	479947
571	480391
572	465029
573	441230
574	414175
575	415601
576	420384
577	411428
578	405533
579	416773
580	429371
581	432578
582	435577
583	428696
584	415264
585	414551
586	426419
587	445848
588	460454
589	471143
590	486022
591	513139
592	532699
593	541553
594	543338
595	534509
596	523477
597	497124
598	487956
599	500816
600	509633
601	507582
602	493577
603	481527
604	463137
605	457661
606	451588
607	439117
608	421709
609	417056
610	415372
611	403973
612	378868
613	357016
614	347591
615	335315
616	307840
617	286354
618	269264
619	250750
620	230572
621	217480
622	212830
623	206859
624	201293
625	195610
626	190226
627	180258
628	174141
629	168268
630	165812
631	162909
632	157416
633	157290
634	154970
635	152915
636	144743
637	135063
638	131808
639	132855
640	132081
641	125426
642	111082
643	107015
644	110765
645	113708
646	113626
647	113138
648	112978
649	114083
650	121269
651	129204
652	128354
653	118418
654	113046
655	110725
656	109136
657	109519
658	110072
659	112182
660	113965
661	114851
662	118136
663	122394
664	127219
665	131988
666	133318
667	128070
668	122880
669	126402
670	127991
671	131765
672	136515
673	133019
674	124724
675	119332
676	118769
677	115116
678	117900
679	120271
680	113117
681	111365
682	114811
683	109526
684	105009
685	103926
686	97532
687	93083
688	91666
689	89677
690	88619
691	82280
692	79457
693	82345
694	83304
695	82817
696	83372
697	80874
698	80643
699	78815
700	75169
701	69842
702	65289
703	66693
704	69775
705	68451
706	71242
707	75442
708	73873
709	68043
710	61928
711	60956
712	58650
713	54510
714	54335
715	56481
716	57969
717	55305
718	50167
719	49834
720	52579
721	52830
722	54454
723	56393
724	57418
725	56316
726	57481
727	59000
728	58647
729	55745
730	56735
731	58165
732	55727
733	55092
734	50912
735	51282
736	55374
737	57001
738	52253
739	44814
740	43565
741	46934
742	51083
743	51113
744	54210
745	55410
746	53597
747	49089
748	48211
749	51270
750	52265
751	46321
752	38516
753	36637
754	40768
755	44941
756	48361
757	53980
758	53772
759	50289
760	43561
761	42248
762	41475
763	38938
764	37242
765	37165
766	32449
767	32164
768	36136
769	33559
770	30157
771	30294
772	30434
773	29347
774	30811
775	33480
776	31162
777	27561
778	27841
779	30144
780	29649
781	31160
782	31243
783	27704
784	25466
785	24812
786	24593
787	28579
788	31594
789	32460
790	27898
791	22630
792	22141
793	25872
794	29657
795	28275
796	27085
797	26487
798	22907
799	18652
800	18609
801	21079
802	22095
803	22120
804	21889
805	22229
806	19570
807	17958
808	18864
809	19358
810	19209
811	19456
812	21578
813	24699
814	24504
815	20727
816	20888
817	21475
818	19585
819	16893
820	18624
821	20368
822	19602
823	17804
824	17654
825	24173
826	24590
827	21100
828	20351
829	20390
830	18574
831	15787
832	14048
833	16168
834	18843
835	20510
836	21470
837	22028
838	23124
839	24284
840	22671
841	21202
842	21593
843	20393
844	18124
845	16180
846	17763
847	20972
848	22352
849	20938
850	21187
851	18879
852	20288
853	22583
854	17669
855	14644
856	15800
857	17634
858	18797
859	18807
860	16676
861	17049
862	16259
863	14390
864	13245
865	13018
866	12866
867	13064
868	14532
869	14320
870	14461
871	14573
872	13102
873	15682
874	16108
875	18959
876	21628
877	21698
878	17759
879	16239
880	17337
881	17486
882	16761
883	14327
884	18566
885	19573
886	15219
887	12463
888	13379
889	16875
890	17890
891	18088
892	17723
893	16357
894	14671
895	16294
896	19224
897	21209
898	15768
899	13216
900	13351
901	11978
902	10877
903	12631
904	15173
905	17681
906	15068
907	12757
908	17036
909	15693
910	14311
911	17145
912	15867
913	14133
914	13397
915	14176
916	13844
917	13321
918	12962
919	12995
920	13339
921	16069
922	16439
923	14852
924	12065
925	10550
926	11361
927	12637
928	14969
929	14887
930	13952
931	12717
932	13867
933	12679
934	13393
935	15017
936	16302
937	18704
938	17542
939	17151
940	13141
941	12267
942	15396
943	15740
944	15802
945	16156
946	20242
947	20504
948	19256
949	18442
950	16593
951	17100
952	16926
953	16732
954	15270
955	13811
956	12303
957	12475
958	12744
959	13057
960	14087
961	14365
962	14414
963	13908
964	12290
965	11675
966	12530
967	14109
968	13086
969	12656
970	13317
971	14013
972	12138
973	13712
974	15824
975	17954
976	23705
977	22325
978	21855
979	19684
980	14497
981	11869
982	15874
983	17803
984	19688
985	16221
986	15477
987	17964
988	17235
989	15388
990	15403
991	14198
992	14773
993	14176
994	14169
995	13124
996	13616
997	15928
998	19733
999	17546
1000	13739
1001	12102
1002	13767
1003	13789
1004	13115
1005	12975
1006	13630
1007	13451
1008	11659
1009	11966
1010	15199
1011	19870
1012	20380
1013	18683
1014	16745
1015	16837
1016	15211
1017	12878
1018	12022
1019	13240
1020	13670
1021	14931
1022	12776
1023	13983
1024	15778