1	6033
2	6436
3	6578
4	6333
5	5854
6	5788
7	5591
8	5588
9	5930
10	6171
11	6313
12	6013
13	5696
14	5627
15	6272
16	6485
17	6470
18	6138
19	6125
20	6614
21	7240
22	7340
23	7105
24	6591
25	6511
26	7069
27	7672
28	7888
29	7384
30	6993
31	6617
32	6093
33	6087
34	6270
35	6288
36	6129
37	6149
38	6118
39	6490
40	6592
41	6857
42	6895
43	6900
44	6636
45	6239
46	5530
47	5090
48	5278
49	5548
50	5882
51	6179
52	6396
53	6548
54	6456
55	6328
56	6289
57	6483
58	6328
59	6049
60	6021
61	5957
62	5998
63	6164
64	6313
65	6445
66	6536
67	6535
68	6574
69	6626
70	6645
71	6937
72	7036
73	7018
74	6856
75	6752
76	6704
77	6905
78	7212
79	7639
80	7822
81	7652
82	7545
83	7549
84	7201
85	7247
86	7429
87	7614
88	7712
89	7606
90	7906
91	8352
92	8546
93	9227
94	10435
95	11243
96	10649
97	9171
98	7978
99	7630
100	8209
101	8577
102	9512
103	9594
104	9125
105	7958
106	7065
107	6609
108	6507
109	6668
110	6810
111	6558
112	6456
113	6316
114	6212
115	6181
116	6212
117	6337
118	6658
119	6770
120	6550
121	6762
122	6790
123	7012
124	7075
125	7447
126	7310
127	6926
128	6667
129	6873
130	7560
131	8331
132	8446
133	8005
134	7406
135	7758
136	7972
137	8402
138	8229
139	7863
140	8175
141	8467
142	8526
143	8433
144	7858
145	7300
146	6905
147	6909
148	7614
149	8262
150	8379
151	8502
152	8864
153	8847
154	9060
155	8773
156	8555
157	8516
158	9159
159	9589
160	9953
161	9384
162	8738
163	7926
164	7823
165	7847
166	8438
167	8716
168	8504
169	8470
170	8378
171	8388
172	8050
173	8253
174	8287
175	8093
176	7952
177	7941
178	7869
179	8478
180	8900
181	9221
182	8714
183	8279
184	7727
185	7775
186	8028
187	8059
188	7897
189	7753
190	8118
191	8354
192	8429
193	8195
194	8194
195	8441
196	8941
197	9241
198	9162
199	8940
200	8299
201	7906
202	7470
203	7423
204	7761
205	8011
206	8051
207	8426
208	8769
209	9139
210	9167
211	9347
212	9666
213	10243
214	10563
215	11197
216	10906
217	10530
218	10465
219	10448
220	10325
221	10675
222	11098
223	10940
224	9578
225	8603
226	8297
227	9384
228	10017
229	10158
230	10083
231	9906
232	9657
233	9249
234	9347
235	9768
236	10478
237	10450
238	9809
239	9115
240	9156
241	9453
242	10054
243	10372
244	10628
245	10065
246	9819
247	9730
248	10026
249	10113
250	9726
251	10287
252	10846
253	11140
254	11146
255	10867
256	10502
257	10005
258	9674
259	10070
260	10554
261	10996
262	10940
263	10619
264	10171
265	10385
266	10560
267	10838
268	10905
269	10951
270	11057
271	11846
272	12465
273	12229
274	12030
275	11741
276	11526
277	11426
278	11417
279	11721
280	12077
281	12388
282	12614
283	12209
284	11789
285	11227
286	11081
287	10717
288	10375
289	10542
290	11190
291	12745
292	13171
293	12718
294	11977
295	11467
296	11797
297	12219
298	12671
299	12933
300	13101
301	13414
302	13535
303	13767
304	13781
305	13165
306	13025
307	13080
308	13231
309	13532
310	13257
311	12633
312	12309
313	12766
314	13118
315	13584
316	13984
317	13978
318	13583
319	13453
320	14390
321	14712
322	14168
323	13742
324	13987
325	14242
326	14251
327	14252
328	14272
329	14335
330	14594
331	15208
332	15909
333	15431
334	14401
335	13571
336	13371
337	13768
338	14993
339	16579
340	17669
341	18580
342	18897
343	18746
344	17683
345	17026
346	16405
347	16422
348	15673
349	15325
350	14533
351	14048
352	14203
353	15201
354	16498
355	15908
356	14603
357	13869
358	14083
359	15657
360	17283
361	17897
362	16996
363	16443
364	16690
365	17334
366	16861
367	16022
368	15913
369	17023
370	18265
371	18524
372	17246
373	17326
374	18224
375	18142
376	17455
377	16314
378	15725
379	15638
380	15663
381	15043
382	14843
383	14309
384	14537
385	15194
386	16495
387	17795
388	18770
389	18822
390	17998
391	17512
392	17466
393	18607
394	19979
395	20936
396	21593
397	22475
398	23069
399	22627
400	22317
401	22311
402	21852
403	21011
404	19823
405	18013
406	18527
407	20016
408	21937
409	21894
410	22218
411	21945
412	22174
413	22654
414	23735
415	24454
416	24834
417	23608
418	21857
419	21427
420	22161
421	23280
422	23484
423	23902
424	23696
425	22460
426	21542
427	21799
428	23097
429	23485
430	23052
431	21883
432	22600
433	24282
434	24682
435	23606
436	23559
437	24284
438	24032
439	24291
440	25452
441	26444
442	27354
443	27767
444	27193
445	26429
446	26071
447	25755
448	26562
449	27138
450	27729
451	26639
452	24521
453	23468
454	25048
455	27007
456	27906
457	28029
458	28307
459	27144
460	26908
461	27390
462	26160
463	25228
464	24101
465	25194
466	27254
467	29749
468	30776
469	30602
470	29007
471	28968
472	29455
473	29758
474	30278
475	31730
476	32829
477	32577
478	31381
479	31762
480	33566
481	34164
482	33004
483	31702
484	31148
485	31133
486	32359
487	34159
488	36006
489	36943
490	35950
491	35475
492	34187
493	34341
494	35766
495	37606
496	37759
497	36347
498	36742
499	35556
500	35044
501	35424
502	34003
503	32808
504	33816
505	36593
506	39652
507	40922
508	39825
509	37812
510	36307
511	36305
512	39250
513	42360
514	40915
515	38713
516	37823
517	38581
518	40345
519	41237
520	40062
521	37664
522	37471
523	39461
524	42271
525	42995
526	42651
527	42861
528	44297
529	44871
530	44439
531	44807
532	43530
533	43448
534	45001
535	47003
536	47015
537	46475
538	47246
539	47544
540	47465
541	47683
542	46719
543	45332
544	44583
545	45097
546	45638
547	45564
548	44182
549	43079
550	46025
551	48890
552	48427
553	46651
554	44475
555	44865
556	45873
557	47877
558	48141
559	48682
560	50631
561	50198
562	50755
563	50967
564	52385
565	51166
566	50253
567	48978
568	48762
569	48263
570	48410
571	49524
572	51731
573	53291
574	52851
575	53087
576	53179
577	52006
578	50123
579	50843
580	54653
581	57919
582	57322
583	53452
584	50788
585	51088
586	52657
587	52425
588	51714
589	51891
590	51430
591	50489
592	50622
593	50393
594	49065
595	48191
596	48775
597	47753
598	46414
599	46433
600	47621
601	47438
602	47085
603	47760
604	47611
605	47500
606	48545
607	48999
608	47380
609	44930
610	43546
611	41845
612	41557
613	44531
614	47090
615	45940
616	43304
617	44966
618	46360
619	46081
620	42989
621	41450
622	43638
623	45961
624	46915
625	45849
626	43469
627	40436
628	39607
629	39041
630	37135
631	35091
632	35661
633	37429
634	37993
635	38124
636	38866
637	39882
638	38017
639	35916
640	36078
641	38322
642	39845
643	39976
644	39294
645	40204
646	39361
647	38341
648	38020
649	35748
650	34108
651	32731
652	32582
653	36027
654	37247
655	35948
656	35256
657	34617
658	32756
659	32936
660	34431
661	36376
662	35978
663	33427
664	31405
665	30126
666	31203
667	32260
668	31983
669	31814
670	31697
671	31352
672	30058
673	31069
674	32573
675	32401
676	32119
677	31975
678	32312
679	34672
680	34938
681	32630
682	31687
683	29584
684	28811
685	28479
686	26950
687	27786
688	28245
689	29521
690	31312
691	30733
692	28297
693	25638
694	23586
695	24049
696	25234
697	26477
698	27464
699	27755
700	26814
701	27096
702	28763
703	28303
704	26213
705	26281
706	25940
707	25058
708	24682
709	23951
710	25006
711	26498
712	26629
713	25083
714	23607
715	22734
716	23107
717	22285
718	22716
719	24769
720	26989
721	27939
722	25349
723	21527
724	20233
725	20195
726	22651
727	23101
728	21162
729	21657
730	24076
731	25233
732	23076
733	22594
734	23411
735	24016
736	22388
737	21815
738	22868
739	23326
740	22086
741	20340
742	19488
743	18628
744	18759
745	19931
746	19886
747	20107
748	22359
749	22638
750	19656
751	17130
752	17943
753	19839
754	20694
755	20625
756	19966
757	20535
758	19883
759	19571
760	20732
761	20686
762	19350
763	19492
764	21490
765	20318
766	18808
767	18856
768	18285
769	17460
770	16522
771	16226
772	18099
773	19819
774	16450
775	15530
776	17300
777	18386
778	18636
779	19016
780	20468
781	20592
782	19904
783	19184
784	17180
785	15297
786	14231
787	15960
788	17986
789	18160
790	18349
791	18879
792	19464
793	19378
794	18972
795	19258
796	18297
797	16453
798	15401
799	15242
800	15815
801	17596
802	17391
803	15511
804	14059
805	14271
806	15417
807	14597
808	14003
809	15962
810	17151
811	16196
812	17239
813	17021
814	15319
815	14913
816	16563
817	17425
818	15842
819	15051
820	15558
821	16397
822	15941
823	17250
824	17763
825	16073
826	14545
827	13795
828	14319
829	14136
830	13193
831	12866
832	13076
833	11855
834	11817
835	12675
836	14143
837	14422
838	13186
839	12982
840	13062
841	15068
842	17114
843	15412
844	13570
845	12419
846	11699
847	12041
848	12019
849	11111
850	10795
851	12487
852	13999
853	13578
854	12144
855	10848
856	11199
857	12354
858	11804
859	11641
860	12836
861	14294
862	15323
863	15155
864	13389
865	12961
866	13458
867	12616
868	12390
869	13455
870	12588
871	11774
872	12401
873	13258
874	12244
875	12031
876	11632
877	11406
878	11854
879	11189
880	12009
881	11990
882	10342
883	10430
884	11446
885	11213
886	11599
887	11930
888	12323
889	11967
890	11408
891	9740
892	9118
893	9528
894	8932
895	8351
896	9922
897	12538
898	12400
899	11927
900	11413
901	10746
902	11846
903	12509
904	11808
905	10818
906	11267
907	10487
908	10970
909	12487
910	12630
911	11975
912	10816
913	9486
914	10235
915	11838
916	11643
917	10652
918	10489
919	9407
920	9077
921	9885
922	10211
923	10982
924	13835
925	12522
926	13270
927	13945
928	13930
929	13049
930	12183
931	10768
932	9909
933	10484
934	9657
935	8538
936	9933
937	10408
938	11573
939	12271
940	11958
941	12055
942	12408
943	11832
944	11361
945	10682
946	10214
947	9958
948	9569
949	8533
950	9256
951	9967
952	10994
953	10781
954	10082
955	10135
956	11447
957	10224
958	12253
959	13553
960	11926
961	10140
962	8350
963	8196
964	9707
965	9923
966	10627
967	11221
968	10959
969	10302
970	10213
971	9975
972	9084
973	8646
974	6988
975	8065
976	9282
977	9900
978	11403
979	11118
980	11265
981	10507
982	10316
983	10005
984	9662
985	10352
986	9499
987	9878
988	9565
989	9798
990	9036
991	9793
992	10285
993	10698
994	9810
995	10298
996	10680
997	10231
998	9524
999	9809
1000	9927
1001	8879
1002	8990
1003	8239
1004	7305
1005	8381
1006	10084
1007	9921
1008	8014
1009	7320
1010	9916
1011	10055
1012	9129
1013	8909
1014	8058
1015	8716
1016	9636
1017	9716
1018	7986
1019	9070
1020	9803
1021	9084
1022	7171
1023	8129
1024	8810