1	4881
2	4509
3	4409
4	4493
5	4539
6	4695
7	4883
8	4572
9	4737
10	4722
11	4865
12	4736
13	4932
14	4886
15	4957
16	4836
17	4740
18	4416
19	4307
20	4637
21	4763
22	5005
23	5206
24	5191
25	5226
26	5522
27	5565
28	5987
29	5956
30	5962
31	5931
32	5679
33	5546
34	5498
35	5694
36	5943
37	6133
38	6099
39	5641
40	5405
41	5558
42	5891
43	5932
44	5705
45	5602
46	5213
47	5147
48	5231
49	4695
50	4532
51	4582
52	4939
53	5442
54	5684
55	5897
56	5673
57	5768
58	5624
59	5091
60	4864
61	4968
62	4969
63	5206
64	5215
65	5285
66	5436
67	5646
68	6026
69	6165
70	6124
71	5815
72	5482
73	5569
74	5629
75	6027
76	6381
77	6581
78	6515
79	6126
80	5321
81	4970
82	5079
83	5798
84	6146
85	6244
86	5983
87	5492
88	5420
89	5523
90	6135
91	6251
92	6002
93	5407
94	5087
95	4987
96	5159
97	5543
98	5798
99	5761
100	5629
101	5220
102	5284
103	5148
104	5703
105	6079
106	6350
107	6430
108	6280
109	5813
110	5825
111	5649
112	5490
113	5223
114	4916
115	4883
116	4827
117	5000
118	5365
119	6040
120	6672
121	7676
122	7655
123	7114
124	6369
125	5887
126	5538
127	5512
128	5743
129	5925
130	6375
131	6449
132	6577
133	6202
134	5657
135	5802
136	5968
137	6370
138	6414
139	6157
140	5978
141	6024
142	5528
143	5306
144	5172
145	5473
146	5863
147	5954
148	6166
149	6148
150	6304
151	6320
152	6286
153	6357
154	6487
155	6400
156	6361
157	6244
158	6324
159	6236
160	6471
161	6379
162	6242
163	5663
164	6069
165	6918
166	8086
167	8833
168	8742
169	8206
170	7039
171	6179
172	5500
173	5446
174	5585
175	5775
176	6268
177	6464
178	6433
179	6462
180	5918
181	5688
182	5749
183	6284
184	6557
185	6959
186	7186
187	7226
188	7112
189	7085
190	7585
191	7858
192	7407
193	6736
194	6200
195	6216
196	6422
197	6871
198	7103
199	7212
200	6911
201	6703
202	6260
203	6689
204	7236
205	7417
206	7480
207	7556
208	7216
209	6692
210	6222
211	6251
212	6705
213	6685
214	6173
215	6013
216	6023
217	6380
218	6894
219	7137
220	7633
221	8133
222	8506
223	8969
224	8580
225	8490
226	7975
227	7787
228	7190
229	7074
230	7043
231	7176
232	7565
233	7842
234	8299
235	8589
236	8469
237	7989
238	7874
239	8073
240	8627
241	9060
242	8711
243	8364
244	8034
245	7703
246	7344
247	7266
248	7761
249	8378
250	8677
251	9059
252	9627
253	9976
254	9702
255	8765
256	7720
257	7050
258	7602
259	8503
260	8899
261	8475
262	7715
263	7398
264	8018
265	8855
266	8913
267	8507
268	7814
269	7591
270	7559
271	7598
272	7251
273	6980
274	6928
275	7475
276	8118
277	8863
278	9196
279	9144
280	9428
281	9646
282	10456
283	10873
284	10943
285	10844
286	10842
287	11111
288	10929
289	10600
290	10084
291	9657
292	9468
293	9582
294	9797
295	10165
296	10854
297	11136
298	10502
299	9689
300	9702
301	10232
302	10562
303	10375
304	10180
305	9881
306	9464
307	9015
308	8970
309	9190
310	8801
311	8616
312	8918
313	9713
314	9741
315	9330
316	8880
317	8829
318	8941
319	9271
320	9757
321	10193
322	10493
323	10364
324	9652
325	8660
326	8360
327	8573
328	8856
329	9130
330	9836
331	11305
332	12320
333	12427
334	11894
335	11357
336	11629
337	12692
338	13617
339	13763
340	13428
341	12527
342	11755
343	11900
344	13150
345	13966
346	13321
347	12430
348	11957
349	11975
350	12052
351	12445
352	13418
353	13642
354	13460
355	13609
356	13650
357	13482
358	13548
359	13576
360	13706
361	13415
362	12979
363	12887
364	13418
365	14172
366	15329
367	16569
368	17480
369	17562
370	16532
371	14818
372	13662
373	13749
374	15184
375	16637
376	17542
377	16893
378	14950
379	13519
380	13583
381	14192
382	14504
383	14822
384	15317
385	15449
386	15354
387	15591
388	16185
389	16639
390	17011
391	17649
392	17132
393	17112
394	17641
395	17741
396	17056
397	16438
398	16412
399	15363
400	13891
401	13219
402	13184
403	13431
404	13148
405	14008
406	15642
407	16244
408	17133
409	17690
410	17950
411	16962
412	16329
413	16752
414	17506
415	17711
416	17135
417	16777
418	17420
419	18050
420	18061
421	17638
422	18616
423	19324
424	19308
425	18106
426	16955
427	16260
428	16798
429	17559
430	18082
431	18568
432	19305
433	19518
434	18708
435	18022
436	17672
437	18009
438	17472
439	17036
440	17443
441	18597
442	19423
443	20130
444	21813
445	22432
446	21543
447	21270
448	22033
449	21250
450	19800
451	19851
452	20235
453	21034
454	22331
455	23921
456	24318
457	23874
458	22710
459	21148
460	19744
461	19876
462	20764
463	21934
464	24092
465	25845
466	25681
467	23577
468	21673
469	20980
470	20857
471	22313
472	23965
473	25539
474	25673
475	25091
476	25535
477	26615
478	26387
479	27309
480	28151
481	28794
482	29193
483	29302
484	28405
485	25581
486	23666
487	22952
488	23271
489	24209
490	26130
491	27318
492	26391
493	25996
494	26531
495	27988
496	28067
497	27214
498	27401
499	27785
500	28923
501	28736
502	27286
503	26746
504	27487
505	29827
506	30942
507	30057
508	29703
509	30534
510	31493
511	30709
512	29464
513	30134
514	31834
515	33649
516	34833
517	35136
518	33930
519	31778
520	30874
521	31409
522	32760
523	33248
524	33036
525	32407
526	33168
527	34433
528	34827
529	33254
530	32298
531	32496
532	32832
533	32823
534	32383
535	33246
536	34131
537	33807
538	33116
539	32584
540	33368
541	34662
542	33369
543	31693
544	32037
545	33096
546	33051
547	33554
548	34098
549	35705
550	36588
551	37233
552	38412
553	39143
554	39458
555	39254
556	39084
557	39695
558	39088
559	37407
560	37640
561	37458
562	36391
563	35873
564	37988
565	37889
566	36931
567	37823
568	40095
569	38986
570	38568
571	39991
572	41053
573	41140
574	40892
575	40443
576	38038
577	35668
578	33885
579	35752
580	41180
581	44186
582	43662
583	42397
584	41621
585	40318
586	37291
587	35999
588	37198
589	37599
590	36290
591	34673
592	34498
593	35369
594	35535
595	36415
596	37590
597	36899
598	36633
599	37657
600	37366
601	35759
602	34252
603	34276
604	35193
605	34520
606	32629
607	31754
608	32592
609	33801
610	33012
611	31778
612	34410
613	37426
614	35924
615	33236
616	32491
617	34314
618	34555
619	33978
620	33946
621	33854
622	33966
623	33581
624	32806
625	31959
626	31134
627	30870
628	32366
629	33675
630	34144
631	35168
632	32587
633	29326
634	28769
635	29900
636	31197
637	31926
638	31426
639	30864
640	31390
641	31443
642	28099
643	26446
644	26928
645	28068
646	28587
647	27811
648	29037
649	28403
650	27200
651	26864
652	26489
653	26576
654	25711
655	26842
656	28692
657	28984
658	26933
659	26107
660	27655
661	28193
662	27581
663	25937
664	25085
665	25262
666	25862
667	25532
668	23776
669	21700
670	21550
671	22995
672	24903
673	25124
674	25429
675	23831
676	22547
677	21791
678	23863
679	24230
680	22946
681	23159
682	24586
683	22659
684	21281
685	22206
686	22147
687	22478
688	22216
689	23173
690	24158
691	23863
692	22219
693	20114
694	19861
695	19139
696	19546
697	21308
698	21219
699	20814
700	20877
701	19802
702	18964
703	17910
704	17334
705	17114
706	17500
707	17122
708	17473
709	18816
710	18693
711	18812
712	20075
713	19638
714	18321
715	20308
716	23457
717	22366
718	19995
719	17850
720	17463
721	17195
722	15740
723	15734
724	18117
725	18216
726	16870
727	16101
728	14725
729	15436
730	16741
731	17401
732	16943
733	17381
734	18028
735	18283
736	17706
737	17095
738	17227
739	15882
740	15279
741	15650
742	16026
743	16837
744	16355
745	15424
746	15039
747	15901
748	16217
749	15697
750	15517
751	14802
752	15266
753	16520
754	15701
755	14416
756	12771
757	12664
758	13324
759	14486
760	15152
761	15932
762	15872
763	15224
764	15438
765	15582
766	14398
767	13404
768	12809
769	12896
770	12306
771	12134
772	12461
773	11545
774	10196
775	10686
776	12955
777	14067
778	13936
779	14074
780	14140
781	14895
782	14748
783	13335
784	12384
785	13539
786	14206
787	13476
788	12437
789	11316
790	11188
791	12777
792	13470
793	12967
794	12263
795	12409
796	12975
797	11651
798	10996
799	11734
800	11776
801	11633
802	10333
803	10552
804	11202
805	11420
806	12092
807	12139
808	13397
809	14886
810	13158
811	11591
812	11796
813	11542
814	10513
815	11279
816	13160
817	12565
818	11750
819	11006
820	9577
821	11520
822	13563
823	12705
824	11060
825	12064
826	13714
827	14739
828	15662
829	14158
830	11347
831	11183
832	12366
833	11184
834	10389
835	10577
836	10126
837	9794
838	9736
839	10947
840	11647
841	10539
842	11539
843	10997
844	10496
845	10941
846	12939
847	13626
848	11038
849	9069
850	9438
851	8917
852	8445
853	9226
854	9904
855	10082
856	10166
857	10577
858	10031
859	9963
860	7814
861	6792
862	7230
863	9337
864	10397
865	9081
866	8216
867	9517
868	11947
869	11899
870	12180
871	11911
872	10481
873	10838
874	10782
875	11268
876	10123
877	9152
878	9828
879	11534
880	12257
881	9969
882	8657
883	9424
884	10028
885	9795
886	10768
887	11370
888	9596
889	8645
890	8584
891	8277
892	7401
893	8194
894	8582
895	8917
896	9180
897	8219
898	8697
899	9866
900	9266
901	7861
902	6396
903	6256
904	6418
905	8135
906	10142
907	10647
908	10133
909	9171
910	7613
911	6994
912	6805
913	8610
914	11129
915	12240
916	11716
917	9776
918	9133
919	9681
920	10175
921	10317
922	11094
923	12234
924	11270
925	10078
926	9458
927	8009
928	7042
929	7096
930	7195
931	7839
932	6848
933	6795
934	6881
935	7380
936	9532
937	8963
938	6768
939	6556
940	8605
941	9631
942	9017
943	7871
944	7186
945	7947
946	7952
947	8579
948	8143
949	7680
950	7031
951	7781
952	8880
953	9537
954	9375
955	8121
956	8474
957	9407
958	7736
959	6403
960	6410
961	6269
962	7680
963	9761
964	10387
965	9039
966	8620
967	8511
968	7624
969	7012
970	8118
971	7358
972	7973
973	7193
974	6593
975	8200
976	7966
977	6862
978	7769
979	7230
980	7939
981	6788
982	6320
983	6113
984	6044
985	6952
986	7370
987	8296
988	8544
989	8601
990	8286
991	9267
992	9974
993	8245
994	7225
995	8057
996	7377
997	7021
998	8317
999	8082
1000	6827
1001	7190
1002	7433
1003	6214
1004	6496
1005	6948
1006	6919
1007	5999
1008	5328
1009	4946
1010	6628
1011	8311
1012	9359
1013	9897
1014	8781
1015	7695
1016	7860
1017	9015
1018	8543
1019	8929
1020	7638
1021	6795
1022	5696
1023	6054
1024	7124