1	3232
2	4220
3	5211
4	5616
5	5165
6	4434
7	4094
8	4109
9	4435
10	4923
11	5019
12	5445
13	6272
14	6809
15	6804
16	6357
17	5850
18	5630
19	5880
20	5904
21	5570
22	4686
23	4148
24	3773
25	4062
26	4638
27	5270
28	5306
29	4478
30	4027
31	4008
32	3773
33	3652
34	3409
35	3828
36	4566
37	4771
38	4679
39	4389
40	4195
41	4318
42	4430
43	5014
44	5395
45	6021
46	6134
47	5920
48	5325
49	4935
50	5095
51	5421
52	5999
53	6182
54	5625
55	4599
56	3558
57	2690
58	2263
59	2141
60	2211
61	2048
62	1672
63	1574
64	1990
65	2249
66	2605
67	2930
68	3109
69	3367
70	3499
71	3859
72	4710
73	5616
74	6353
75	6769
76	6035
77	5398
78	4512
79	4356
80	4439
81	4722
82	5124
83	5386
84	5411
85	5114
86	5066
87	5210
88	5188
89	4940
90	4603
91	4199
92	4073
93	4660
94	5258
95	5303
96	4546
97	3462
98	2875
99	3083
100	3790
101	4707
102	5532
103	5971
104	5718
105	5034
106	4491
107	4041
108	3463
109	3077
110	2762
111	2537
112	2688
113	3152
114	3596
115	3889
116	3940
117	3882
118	3796
119	3806
120	3749
121	3853
122	3742
123	3622
124	3513
125	3799
126	3515
127	3151
128	2476
129	2358
130	2495
131	2953
132	3732
133	4659
134	5662
135	6456
136	6323
137	5932
138	5335
139	4789
140	4563
141	4153
142	3565
143	3149
144	3092
145	3413
146	3944
147	4367
148	4991
149	5816
150	6450
151	6379
152	6027
153	4903
154	4210
155	4209
156	4525
157	4417
158	3899
159	3535
160	4133
161	5562
162	7160
163	7985
164	8896
165	9540
166	9223
167	8592
168	7659
169	6773
170	6623
171	6923
172	7432
173	7440
174	7574
175	8472
176	9650
177	10462
178	9624
179	8013
180	7014
181	6368
182	5716
183	5293
184	5524
185	6329
186	7156
187	7838
188	8335
189	8801
190	8734
191	8075
192	7479
193	7904
194	8343
195	8505
196	8229
197	8637
198	9252
199	10168
200	10705
201	10776
202	10501
203	10458
204	10673
205	11125
206	11913
207	12513
208	12281
209	11989
210	11796
211	11933
212	11679
213	11416
214	11524
215	12338
216	12324
217	11528
218	11019
219	11143
220	11578
221	11745
222	12140
223	13229
224	13023
225	12321
226	11375
227	10565
228	9900
229	8839
230	7493
231	6590
232	7178
233	8332
234	8404
235	7386
236	7489
237	7990
238	8795
239	9400
240	9490
241	9555
242	9359
243	9408
244	9352
245	8748
246	8108
247	8462
248	9545
249	9817
250	9522
251	9189
252	9259
253	9341
254	9718
255	10094
256	10315
257	10589
258	11313
259	11844
260	11046
261	9760
262	8403
263	7845
264	8858
265	10417
266	11728
267	11713
268	10133
269	8030
270	6645
271	7191
272	9352
273	11409
274	12435
275	12198
276	11515
277	10330
278	9349
279	8644
280	7990
281	7529
282	8198
283	9126
284	9401
285	8811
286	7354
287	6599
288	6434
289	6935
290	7595
291	9000
292	9680
293	9436
294	9222
295	8825
296	8596
297	7406
298	7111
299	7700
300	8517
301	8908
302	8230
303	6906
304	6389
305	6887
306	7556
307	7771
308	7976
309	8250
310	8742
311	9109
312	8792
313	8918
314	8615
315	8578
316	7604
317	6342
318	6090
319	6620
320	7617
321	7953
322	8184
323	8415
324	7645
325	6197
326	5776
327	6299
328	6502
329	6826
330	7065
331	7247
332	7255
333	6497
334	5818
335	5794
336	6151
337	6833
338	7632
339	8618
340	9336
341	9590
342	9386
343	8669
344	8205
345	8425
346	8320
347	8291
348	7751
349	7905
350	9170
351	10554
352	10902
353	10874
354	10388
355	9644
356	8411
357	6923
358	5994
359	5305
360	5478
361	6296
362	7833
363	8478
364	7857
365	7131
366	7738
367	8219
368	7913
369	7007
370	6385
371	7169
372	9737
373	12516
374	13151
375	11582
376	9756
377	8756
378	8556
379	9010
380	9671
381	10258
382	11170
383	11142
384	10111
385	9461
386	9254
387	8866
388	8471
389	8799
390	10088
391	11471
392	12179
393	11862
394	10502
395	10156
396	10422
397	10717
398	10350
399	10868
400	11463
401	11533
402	10896
403	10302
404	10084
405	10013
406	10010
407	10352
408	11746
409	14061
410	15066
411	13397
412	11332
413	10914
414	11448
415	11514
416	11568
417	12144
418	12679
419	13134
420	15228
421	17092
422	18912
423	20454
424	21231
425	20311
426	18596
427	16627
428	14240
429	12520
430	13129
431	14655
432	16661
433	17203
434	16762
435	17074
436	17511
437	16718
438	15122
439	13226
440	12868
441	12573
442	11846
443	11915
444	13354
445	15221
446	15933
447	14477
448	13421
449	13524
450	14896
451	17092
452	20185
453	22065
454	21837
455	18920
456	15611
457	14427
458	14635
459	14307
460	12202
461	10544
462	9932
463	11792
464	15221
465	17893
466	17826
467	16809
468	17102
469	18668
470	17281
471	13237
472	10580
473	11050
474	12549
475	13754
476	14646
477	15193
478	16882
479	19827
480	20940
481	20050
482	18508
483	18111
484	18529
485	19236
486	19457
487	18495
488	18047
489	18846
490	20112
491	21211
492	21612
493	20929
494	19580
495	18999
496	17132
497	16562
498	18104
499	19783
500	19654
501	16866
502	14665
503	14876
504	16748
505	16942
506	16953
507	18151
508	21235
509	21991
510	19339
511	16188
512	15400
513	15537
514	15074
515	14291
516	13080
517	12548
518	13316
519	14339
520	15082
521	15360
522	14536
523	13618
524	13827
525	12672
526	9582
527	7753
528	8010
529	9830
530	11937
531	13123
532	12850
533	11796
534	11216
535	13380
536	14368
537	12990
538	11436
539	10088
540	8192
541	7307
542	7544
543	7967
544	8558
545	10044
546	12809
547	14167
548	15156
549	14109
550	10775
551	9185
552	9000
553	9377
554	10919
555	11690
556	10171
557	8543
558	8013
559	7848
560	8566
561	8442
562	8140
563	9891
564	11823
565	11695
566	9619
567	7855
568	8352
569	8830
570	9102
571	8951
572	8913
573	7816
574	6380
575	6616
576	7290
577	8104
578	9671
579	11166
580	10248
581	8804
582	7849
583	6447
584	6053
585	5905
586	6864
587	7653
588	6931
589	6034
590	5794
591	5523
592	6084
593	7056
594	8142
595	7945
596	7269
597	6911
598	6424
599	6003
600	6205
601	6139
602	6820
603	6926
604	5921
605	6282
606	5799
607	4845
608	6034
609	9786
610	13060
611	12992
612	11441
613	10597
614	10569
615	10553
616	10581
617	10739
618	9595
619	8196
620	6871
621	5874
622	5914
623	5957
624	6399
625	6502
626	5641
627	5113
628	6183
629	6720
630	6052
631	4763
632	4367
633	4927
634	5518
635	5127
636	3778
637	3238
638	4433
639	4798
640	4425
641	4654
642	4439
643	4108
644	3887
645	3448
646	3156
647	3891
648	5005
649	5610
650	5945
651	6585
652	7585
653	7757
654	6280
655	6433
656	6652
657	6463
658	6214
659	5725
660	6115
661	5832
662	3883
663	3935
664	6164
665	7739
666	7225
667	5800
668	4726
669	4456
670	5072
671	5470
672	4931
673	3974
674	3733
675	4273
676	5129
677	4623
678	3921
679	4444
680	5412
681	4942
682	4655
683	5385
684	7228
685	8186
686	7529
687	6597
688	5143
689	5192
690	5980
691	6206
692	6897
693	8558
694	8707
695	6741
696	5701
697	5444
698	5217
699	4805
700	5668
701	6663
702	4967
703	3803
704	3131
705	2716
706	3948
707	4985
708	3868
709	3434
710	4482
711	5980
712	7520
713	9165
714	8367
715	7382
716	7537
717	8412
718	7617
719	4892
720	3838
721	4321
722	6908
723	8494
724	7932
725	7153
726	8072
727	9055
728	9288
729	9667
730	9128
731	7353
732	6305
733	7567
734	7666
735	7483
736	8228
737	8388
738	7890
739	7413
740	6586
741	6786
742	6243
743	7121
744	6842
745	5230
746	5771
747	6838
748	7592
749	9388
750	9887
751	10426
752	11382
753	11988
754	11704
755	10842
756	10293
757	9341
758	8132
759	8798
760	8618
761	9198
762	9604
763	8592
764	8442
765	8459
766	8136
767	9215
768	9743
769	9811
770	9077
771	7542
772	7380
773	9644
774	10283
775	8194
776	6810
777	6971
778	8640
779	10171
780	9299
781	8265
782	7747
783	7011
784	6317
785	6093
786	7417
787	8404
788	6480
789	6140
790	7176
791	7753
792	10803
793	11439
794	10816
795	11383
796	11383
797	11283
798	10560
799	8683
800	9657
801	13484
802	14042
803	11407
804	10105
805	7805
806	9495
807	11032
808	9911
809	7958
810	8328
811	8772
812	8812
813	10923
814	9752
815	8454
816	8201
817	6466
818	7952
819	11689
820	14205
821	12569
822	10506
823	11187
824	11805
825	9652
826	8824
827	9397
828	11032
829	11179
830	9220
831	7199
832	6882
833	9534
834	10482
835	10013
836	9638
837	7803
838	6602
839	6571
840	6468
841	7088
842	9519
843	9381
844	8849
845	6987
846	6531
847	8707
848	12618
849	11459
850	9149
851	9426
852	9584
853	7457
854	5785
855	5700
856	6143
857	6201
858	5844
859	6036
860	8946
861	8246
862	5019
863	5203
864	5347
865	3902
866	3943
867	4428
868	5088
869	5640
870	6913
871	9555
872	7430
873	4424
874	4065
875	6262
876	7827
877	7089
878	5224
879	4568
880	4574
881	5913
882	6798
883	6929
884	6043
885	5608
886	5277
887	4591
888	4769
889	5528
890	4290
891	3074
892	2303
893	2385
894	4822
895	8358
896	6672
897	4839
898	5507
899	4705
900	4512
901	5294
902	4266
903	4476
904	4888
905	6005
906	7089
907	5507
908	6200
909	4376
910	2960
911	5205
912	6408
913	5505
914	4879
915	5353
916	7184
917	6428
918	5356
919	4128
920	3438
921	4069
922	5722
923	5436
924	5775
925	8192
926	5916
927	4831
928	5320
929	6301
930	4867
931	3527
932	2356
933	3850
934	4553
935	2896
936	3261
937	3230
938	4056
939	5240
940	4776
941	4540
942	5073
943	5521
944	4186
945	3482
946	4842
947	3798
948	3206
949	5978
950	4927
951	3601
952	3865
953	3639
954	4017
955	4514
956	4476
957	5249
958	6201
959	4504
960	2677
961	1879
962	3377
963	5610
964	5594
965	5360
966	4394
967	4802
968	5443
969	5743
970	4433
971	3436
972	4336
973	4295
974	3630
975	3594
976	4619
977	3010
978	2166
979	2116
980	2788
981	4326
982	4545
983	2745
984	1959
985	2078
986	3046
987	6146
988	6768
989	5351
990	4871
991	4418
992	3880
993	4510
994	4277
995	5317
996	8191
997	6095
998	4344
999	3350
1000	2882
1001	3952
1002	5352
1003	4725
1004	3874
1005	2947
1006	2925
1007	3585
1008	4490
1009	5808
1010	3333
1011	2459
1012	3233
1013	4104
1014	2694
1015	1798
1016	1631
1017	1730
1018	3371
1019	3944
1020	4923
1021	5367
1022	5703
1023	5259
1024	3356