1	9223
2	8627
3	8410
4	8604
5	9357
6	10099
7	10493
8	9992
9	9454
10	9293
11	9938
12	10288
13	10654
14	10390
15	10441
16	10746
17	11626
18	12547
19	12312
20	11345
21	10542
22	10096
23	10463
24	11215
25	12392
26	13170
27	13578
28	13339
29	12609
30	12527
31	12237
32	12898
33	13947
34	14706
35	14929
36	14501
37	13611
38	13041
39	12544
40	13287
41	13649
42	13850
43	12949
44	12579
45	13792
46	15442
47	16885
48	17682
49	16549
50	15102
51	14105
52	13776
53	15161
54	16561
55	17483
56	17544
57	17173
58	16172
59	15475
60	16140
61	17001
62	17980
63	18618
64	19140
65	19246
66	20045
67	20350
68	21024
69	21322
70	21548
71	21641
72	20837
73	19576
74	18359
75	17864
76	17989
77	18634
78	19352
79	20346
80	21683
81	22507
82	22979
83	23414
84	23416
85	23512
86	23634
87	24048
88	24280
89	24052
90	24010
91	23292
92	22793
93	22460
94	22090
95	22270
96	22110
97	22838
98	23744
99	24627
100	24561
101	23658
102	23079
103	22305
104	22151
105	21851
106	21855
107	21808
108	21752
109	20735
110	20553
111	20088
112	20444
113	20234
114	20151
115	20141
116	20326
117	20118
118	19734
119	19736
120	19472
121	19543
122	19369
123	18558
124	17940
125	17859
126	17563
127	17434
128	17143
129	16763
130	17104
131	17673
132	17794
133	17085
134	16217
135	15974
136	16357
137	16780
138	17051
139	16228
140	15626
141	14849
142	14260
143	14486
144	15182
145	15715
146	16040
147	15753
148	15398
149	15118
150	15025
151	14784
152	14795
153	14199
154	14099
155	13692
156	13926
157	14455
158	14454
159	14460
160	14209
161	13929
162	14263
163	14067
164	13868
165	13136
166	12348
167	11606
168	11189
169	11034
170	10858
171	10678
172	10482
173	10675
174	10498
175	10234
176	10735
177	11327
178	11355
179	11188
180	10502
181	10114
182	9852
183	10631
184	11538
185	12877
186	13748
187	13550
188	12454
189	11556
190	11077
191	10819
192	10446
193	10123
194	9724
195	9755
196	9740
197	9348
198	9109
199	9124
200	8769
201	8558
202	8386
203	8160
204	7919
205	7521
206	6976
207	7191
208	7461
209	7922
210	8560
211	9036
212	9896
213	10361
214	10157
215	9891
216	9586
217	9608
218	9071
219	8483
220	8357
221	8934
222	9493
223	9471
224	9120
225	9207
226	9319
227	9356
228	8880
229	8768
230	9109
231	9273
232	9060
233	8931
234	9468
235	10052
236	10603
237	10768
238	10893
239	10523
240	9738
241	9040
242	8353
243	8563
244	9053
245	9059
246	8582
247	7750
248	7076
249	7012
250	7170
251	7516
252	7832
253	8479
254	9027
255	9470
256	9559
257	8983
258	8492
259	8412
260	8754
261	9428
262	9683
263	10350
264	10466
265	9677
266	8807
267	8391
268	8473
269	8535
270	8663
271	9129
272	9957
273	10450
274	10971
275	9979
276	8543
277	7577
278	6986
279	7102
280	7460
281	8016
282	8776
283	8908
284	8974
285	8613
286	7905
287	7588
288	7535
289	7731
290	7766
291	8075
292	8208
293	7826
294	6821
295	6388
296	6919
297	7848
298	8054
299	7267
300	7009
301	7080
302	7273
303	7572
304	7868
305	8322
306	8749
307	8988
308	8826
309	8889
310	8181
311	7338
312	6680
313	6398
314	6328
315	6450
316	6807
317	7277
318	7846
319	8127
320	9069
321	9861
322	9778
323	8857
324	8334
325	7941
326	7890
327	7188
328	6651
329	6677
330	7682
331	8754
332	9417
333	9641
334	9216
335	8747
336	8544
337	7983
338	8166
339	8032
340	7847
341	7466
342	7235
343	7538
344	7924
345	8100
346	8200
347	8816
348	9249
349	9482
350	9415
351	8702
352	8275
353	7984
354	7645
355	7261
356	7206
357	7408
358	7628
359	7989
360	8332
361	8447
362	8783
363	9491
364	9232
365	8778
366	8492
367	8375
368	8067
369	7803
370	7535
371	7627
372	8129
373	8080
374	8151
375	8184
376	8275
377	8221
378	8344
379	8010
380	7922
381	7706
382	7220
383	6574
384	6344
385	7437
386	8454
387	8784
388	8101
389	6960
390	6485
391	6907
392	7033
393	7082
394	7051
395	7410
396	8041
397	8351
398	8060
399	8272
400	8630
401	8783
402	8478
403	8281
404	8454
405	8551
406	8474
407	7567
408	6829
409	6186
410	6480
411	6872
412	7566
413	8472
414	8634
415	8222
416	7806
417	7927
418	8129
419	7861
420	8060
421	7907
422	7628
423	7632
424	8232
425	8527
426	8799
427	8790
428	8274
429	7435
430	7121
431	7072
432	6608
433	6599
434	6967
435	6946
436	6987
437	7229
438	6924
439	6804
440	7336
441	7783
442	8112
443	8185
444	7723
445	7952
446	9348
447	9767
448	8855
449	7929
450	7952
451	7988
452	7547
453	7128
454	7025
455	7209
456	6974
457	6762
458	7183
459	8080
460	8562
461	8723
462	7824
463	7233
464	6726
465	6991
466	7178
467	7224
468	7474
469	7980
470	7703
471	6782
472	6059
473	6163
474	6656
475	6663
476	6592
477	6809
478	7143
479	7564
480	7514
481	7505
482	7561
483	7444
484	7358
485	7112
486	7121
487	7597
488	8140
489	7979
490	7974
491	7753
492	8096
493	8894
494	9226
495	8748
496	8090
497	8173
498	8763
499	8656
500	8160
501	8251
502	8624
503	9103
504	9249
505	9685
506	9774
507	9630
508	9421
509	8309
510	7376
511	7091
512	7699
513	7804
514	7574
515	7640
516	7943
517	7716
518	7687
519	7725
520	8009
521	7928
522	8061
523	8507
524	8404
525	7857
526	7347
527	7158
528	7559
529	7922
530	7979
531	7415
532	7074
533	7024
534	6509
535	6008
536	5636
537	5342
538	5720
539	6152
540	5876
541	5881
542	6101
543	6418
544	7178
545	7863
546	7803
547	7467
548	6680
549	6397
550	6246
551	6468
552	6805
553	6722
554	6276
555	6662
556	6752
557	7511
558	7549
559	7858
560	8217
561	8458
562	8195
563	7619
564	7524
565	8425
566	9417
567	8344
568	6762
569	5878
570	5979
571	6227
572	6681
573	7654
574	8083
575	7632
576	7186
577	7174
578	7751
579	7693
580	7289
581	7230
582	7603
583	8006
584	7984
585	8047
586	7752
587	7911
588	8436
589	8287
590	8484
591	8551
592	7580
593	6730
594	6460
595	6452
596	7261
597	6862
598	6938
599	7521
600	8039
601	8602
602	8135
603	7780
604	8358
605	7801
606	7140
607	7585
608	8871
609	9477
610	9352
611	8970
612	9226
613	9637
614	9562
615	9612
616	9389
617	8590
618	8147
619	7761
620	7669
621	7457
622	7125
623	6888
624	6216
625	6504
626	6300
627	6197
628	6870
629	7909
630	8270
631	8051
632	7201
633	5921
634	5251
635	5328
636	5483
637	5997
638	6383
639	6696
640	6531
641	6327
642	7053
643	7638
644	6771
645	6428
646	7095
647	7198
648	6950
649	6365
650	6406
651	6618
652	5982
653	5669
654	5542
655	6108
656	6557
657	6409
658	6442
659	6277
660	5520
661	5418
662	6156
663	7280
664	7414
665	7089
666	6544
667	5990
668	6678
669	7605
670	7147
671	7007
672	7482
673	7921
674	7542
675	6703
676	7037
677	7370
678	7947
679	8323
680	7564
681	7078
682	7185
683	6603
684	6453
685	6647
686	6116
687	5683
688	5368
689	5745
690	6641
691	6928
692	7782
693	7604
694	6798
695	6873
696	6994
697	6114
698	5974
699	6914
700	7373
701	7278
702	7127
703	6369
704	6023
705	7017
706	7662
707	8564
708	8313
709	7039
710	6528
711	7587
712	7996
713	7493
714	7373
715	7749
716	8955
717	8793
718	8425
719	7925
720	7396
721	7211
722	7484
723	7027
724	7175
725	8209
726	7712
727	6921
728	7932
729	8083
730	6253
731	5780
732	6277
733	6125
734	6242
735	6923
736	7111
737	7785
738	8421
739	7616
740	6551
741	6412
742	6742
743	6926
744	6715
745	6658
746	6604
747	6822
748	6744
749	6999
750	7364
751	7020
752	6399
753	5629
754	5390
755	6460
756	7817
757	7473
758	6571
759	6305
760	7737
761	8495
762	7332
763	5596
764	5075
765	6178
766	6029
767	5329
768	5945
769	7146
770	7650
771	7230
772	6303
773	5723
774	6695
775	6850
776	6497
777	5659
778	5200
779	5502
780	6200
781	5430
782	4280
783	4172
784	4229
785	4392
786	4520
787	5455
788	6445
789	6774
790	6675
791	7141
792	7263
793	6254
794	5557
795	6320
796	7341
797	7291
798	6931
799	7505
800	8130
801	8074
802	6793
803	6369
804	6296
805	7463
806	7616
807	7107
808	7439
809	7121
810	6248
811	6496
812	6835
813	6225
814	4518
815	4656
816	4489
817	4124
818	5316
819	6365
820	6022
821	6011
822	6877
823	7449
824	7584
825	7336
826	7253
827	6657
828	6714
829	6891
830	6127
831	6312
832	6850
833	7803
834	8108
835	9129
836	9025
837	7796
838	7548
839	7539
840	7559
841	6526
842	6575
843	8009
844	7660
845	7741
846	8243
847	7630
848	6948
849	6131
850	5203
851	5397
852	7237
853	8952
854	8714
855	8276
856	7910
857	7103
858	5959
859	5870
860	5639
861	5886
862	6238
863	6048
864	6988
865	7006
866	6259
867	5211
868	5078
869	6423
870	7058
871	6430
872	6047
873	5569
874	4987
875	5502
876	6375
877	5869
878	5037
879	5281
880	5969
881	5885
882	5888
883	5892
884	5945
885	6197
886	7812
887	9166
888	8625
889	8145
890	7549
891	6176
892	6026
893	6858
894	8124
895	8150
896	8026
897	8019
898	7732
899	5425
900	5702
901	6816
902	7034
903	7648
904	7143
905	6130
906	6391
907	5421
908	5503
909	6331
910	7820
911	7352
912	7247
913	6763
914	6123
915	6107
916	5287
917	5500
918	5902
919	5908
920	5898
921	5918
922	7355
923	6490
924	6035
925	6554
926	6904
927	6870
928	6036
929	7890
930	10075
931	10975
932	9696
933	7220
934	5899
935	6641
936	6263
937	5932
938	5957
939	6000
940	5722
941	5987
942	6056
943	5970
944	6667
945	6508
946	6172
947	5273
948	4376
949	4714
950	5378
951	5939
952	6254
953	6553
954	6514
955	6472
956	5724
957	4757
958	5392
959	5944
960	6557
961	7415
962	8180
963	7041
964	5910
965	4771
966	6336
967	7104
968	5582
969	4599
970	5866
971	7296
972	7764
973	8002
974	7791
975	6899
976	5849
977	6035
978	5559
979	6187
980	8660
981	8068
982	6861
983	5880
984	5272
985	5185
986	5767
987	5884
988	5871
989	5459
990	5848
991	6859
992	6389
993	5623
994	5267
995	5953
996	7130
997	6312
998	5575
999	5463
1000	4739
1001	4943
1002	6319
1003	6054
1004	6043
1005	8108
1006	8348
1007	5896
1008	4332
1009	5030
1010	6516
1011	7064
1012	6019
1013	7603
1014	8169
1015	7981
1016	6716
1017	5886
1018	6481
1019	7376
1020	6289
1021	5531
1022	6239
1023	5325
1024	4621