1	7096
2	7387
3	7082
4	6486
5	6117
6	5991
7	6420
8	6406
9	6408
10	6415
11	6409
12	6204
13	6190
14	5836
15	5479
16	5277
17	4984
18	4939
19	5071
20	5302
21	5793
22	5997
23	6209
24	5705
25	4930
26	4432
27	4394
28	4872
29	5076
30	5170
31	4866
32	4549
33	4412
34	4644
35	4916
36	5270
37	5390
38	5731
39	5987
40	6349
41	6706
42	6859
43	6542
44	6193
45	6022
46	5705
47	5630
48	6292
49	7023
50	7278
51	6982
52	6260
53	5801
54	5729
55	6010
56	6457
57	7291
58	7485
59	7361
60	7215
61	6553
62	5973
63	6054
64	6115
65	6110
66	5874
67	5542
68	5590
69	5821
70	5891
71	5568
72	5401
73	5275
74	5712
75	6277
76	6801
77	7461
78	7382
79	6917
80	6363
81	6331
82	6799
83	7123
84	6949
85	6904
86	7069
87	7165
88	7006
89	6414
90	6411
91	6124
92	5881
93	5260
94	5410
95	5401
96	5493
97	5165
98	4971
99	4692
100	4652
101	4813
102	5216
103	5407
104	5892
105	6205
106	6494
107	6205
108	5804
109	5188
110	5073
111	4933
112	5329
113	5796
114	6209
115	6599
116	6373
117	6157
118	5959
119	6258
120	6211
121	6461
122	6488
123	6778
124	6993
125	7446
126	7703
127	7848
128	7764
129	7328
130	6774
131	6688
132	6861
133	7230
134	7105
135	6960
136	6467
137	6532
138	6717
139	6587
140	6396
141	6646
142	7010
143	7648
144	7587
145	7085
146	6928
147	6880
148	6624
149	6510
150	6549
151	7428
152	8094
153	7929
154	7617
155	7070
156	6804
157	6865
158	6947
159	6809
160	6786
161	6547
162	6982
163	7215
164	7994
165	8160
166	8039
167	8132
168	8385
169	8408
170	8660
171	8696
172	8440
173	8238
174	8040
175	8524
176	9047
177	8969
178	7575
179	6716
180	6520
181	6766
182	7243
183	7712
184	8231
185	8857
186	8990
187	8627
188	8150
189	7696
190	7877
191	7788
192	8162
193	8064
194	7963
195	7867
196	7750
197	8023
198	8116
199	7792
200	7312
201	7363
202	7559
203	8095
204	8548
205	9153
206	9086
207	8997
208	8494
209	7768
210	7117
211	7075
212	7626
213	8466
214	8550
215	8575
216	8250
217	8144
218	8084
219	7972
220	8155
221	8126
222	8559
223	9360
224	9782
225	9956
226	9325
227	9424
228	9328
229	9001
230	9018
231	8376
232	8358
233	8612
234	9115
235	9147
236	8981
237	8594
238	8114
239	8034
240	8421
241	8990
242	9559
243	10240
244	9816
245	8978
246	8449
247	8383
248	8453
249	8522
250	8490
251	8716
252	8367
253	8037
254	7606
255	8098
256	8865
257	9507
258	9744
259	9696
260	9557
261	9242
262	8899
263	9602
264	10701
265	11516
266	11369
267	10632
268	10697
269	10710
270	10271
271	9899
272	9690
273	9244
274	8782
275	8514
276	8537
277	8575
278	8190
279	7640
280	7528
281	8058
282	9161
283	10109
284	10873
285	11235
286	11014
287	10474
288	10328
289	10578
290	10717
291	10859
292	10802
293	11388
294	11464
295	11475
296	11791
297	11703
298	11364
299	11185
300	11612
301	12025
302	12237
303	12156
304	11918
305	11667
306	11824
307	12134
308	11992
309	12109
310	12128
311	11912
312	12155
313	12505
314	12315
315	11884
316	11908
317	11640
318	11196
319	10724
320	11257
321	12793
322	13522
323	13348
324	13347
325	12696
326	12424
327	12957
328	13831
329	14240
330	14102
331	13223
332	12352
333	11155
334	10119
335	9813
336	9599
337	9815
338	10735
339	11237
340	11505
341	11478
342	10758
343	10499
344	11404
345	12682
346	13472
347	14697
348	15448
349	15470
350	14687
351	13508
352	13192
353	13192
354	13579
355	14375
356	15529
357	15825
358	16153
359	16683
360	17141
361	17301
362	16877
363	17130
364	17051
365	16596
366	15326
367	13997
368	13695
369	14332
370	15652
371	16157
372	15499
373	14454
374	14061
375	13967
376	14465
377	14500
378	14306
379	14173
380	14282
381	14930
382	15306
383	15779
384	16439
385	17276
386	18350
387	17447
388	16270
389	15857
390	16602
391	17424
392	17144
393	16666
394	16260
395	16569
396	15995
397	15891
398	16277
399	16977
400	17527
401	17483
402	17860
403	18349
404	19426
405	19701
406	20125
407	19559
408	21146
409	21745
410	21490
411	19920
412	19239
413	19058
414	19351
415	20004
416	19583
417	18546
418	18755
419	20233
420	21401
421	21222
422	21494
423	21088
424	20963
425	21447
426	21456
427	20014
428	19532
429	19957
430	21967
431	22740
432	22386
433	20918
434	20532
435	21678
436	23102
437	23782
438	24064
439	24379
440	24110
441	23004
442	21840
443	21203
444	21448
445	22300
446	23039
447	22860
448	23007
449	23182
450	22987
451	22712
452	21790
453	21262
454	21521
455	22836
456	24165
457	25232
458	25302
459	24751
460	24221
461	23838
462	24338
463	25332
464	25255
465	24982
466	25294
467	25394
468	24494
469	24317
470	23473
471	23575
472	23638
473	24178
474	25975
475	27627
476	27647
477	28269
478	30105
479	31182
480	29932
481	27182
482	25321
483	26218
484	28824
485	29910
486	29726
487	28806
488	27988
489	27623
490	28287
491	28909
492	29099
493	30058
494	29251
495	29461
496	30771
497	31674
498	32579
499	32950
500	31986
501	30297
502	30080
503	31683
504	33102
505	33398
506	32691
507	32113
508	32943
509	34832
510	36506
511	37900
512	38797
513	38050
514	37092
515	38133
516	40363
517	43048
518	42596
519	39100
520	37118
521	36183
522	37059
523	38461
524	38346
525	36984
526	35713
527	35853
528	36750
529	36876
530	35586
531	35853
532	38142
533	41137
534	42578
535	43081
536	41913
537	40290
538	40998
539	42861
540	44126
541	44473
542	43801
543	42285
544	41984
545	42156
546	40813
547	39141
548	38376
549	39165
550	40524
551	43057
552	45556
553	46929
554	46520
555	44393
556	42014
557	41200
558	41259
559	42631
560	45186
561	46782
562	47863
563	45563
564	42982
565	41341
566	41403
567	43513
568	45668
569	44569
570	43859
571	44218
572	44388
573	43771
574	41946
575	42315
576	44533
577	44689
578	43413
579	43437
580	45116
581	46577
582	45488
583	43859
584	43123
585	42769
586	43447
587	45381
588	45932
589	45365
590	44165
591	42211
592	40200
593	41098
594	44335
595	45468
596	44620
597	44152
598	44057
599	44358
600	43901
601	43418
602	41385
603	39403
604	38942
605	38156
606	38237
607	38942
608	39030
609	40131
610	42964
611	43805
612	42814
613	42359
614	40973
615	38647
616	37056
617	37657
618	37682
619	37552
620	36856
621	37860
622	39648
623	40469
624	39940
625	38138
626	36881
627	37127
628	36716
629	33906
630	33833
631	33895
632	31621
633	31050
634	31461
635	32492
636	33996
637	35279
638	33658
639	31642
640	32734
641	35193
642	35318
643	35789
644	36539
645	36490
646	34438
647	32770
648	33558
649	34144
650	33119
651	32101
652	32175
653	32007
654	30120
655	29052
656	29023
657	29385
658	30265
659	29395
660	27648
661	28821
662	30252
663	28379
664	26318
665	24502
666	24120
667	26623
668	29311
669	29192
670	28787
671	28948
672	28268
673	26158
674	25311
675	25688
676	25724
677	24231
678	25178
679	25613
680	24627
681	24738
682	24772
683	23139
684	23317
685	24578
686	25353
687	26369
688	25826
689	25761
690	26292
691	26291
692	25179
693	23070
694	22539
695	23497
696	24847
697	24494
698	22343
699	21867
700	20376
701	18573
702	18628
703	19867
704	19963
705	20529
706	21503
707	21663
708	20533
709	21430
710	21474
711	20804
712	20676
713	20671
714	19812
715	18606
716	19321
717	20334
718	21081
719	21997
720	23149
721	22047
722	20735
723	20908
724	20233
725	18587
726	19432
727	20557
728	20096
729	18820
730	16776
731	15918
732	17176
733	18785
734	18088
735	17632
736	17666
737	18776
738	18415
739	19210
740	19476
741	19644
742	19204
743	16877
744	15636
745	17284
746	17716
747	16971
748	16655
749	15562
750	15961
751	18286
752	17846
753	15726
754	16113
755	17070
756	17984
757	17493
758	16406
759	16743
760	17289
761	17215
762	15905
763	14980
764	14957
765	15449
766	15885
767	16170
768	16450
769	16936
770	17686
771	16199
772	15161
773	13711
774	11385
775	12000
776	14104
777	15018
778	13940
779	15288
780	17586
781	16761
782	15949
783	16734
784	16575
785	14952
786	13753
787	15593
788	16746
789	15936
790	15867
791	14869
792	13519
793	12791
794	12612
795	13469
796	13201
797	12526
798	11437
799	11269
800	11628
801	13948
802	15304
803	14841
804	13425
805	12290
806	11185
807	11783
808	12628
809	13779
810	14549
811	13871
812	12557
813	11671
814	11608
815	10967
816	12019
817	13169
818	13279
819	13091
820	13213
821	13235
822	13514
823	13510
824	12788
825	13164
826	14671
827	14428
828	12438
829	12235
830	13051
831	12155
832	10166
833	11385
834	14432
835	14239
836	14634
837	13740
838	12990
839	13222
840	13169
841	12578
842	11312
843	10737
844	12008
845	11894
846	11994
847	12687
848	12374
849	12200
850	11347
851	11309
852	11584
853	10908
854	9805
855	9415
856	9325
857	10784
858	12845
859	11968
860	10208
861	10766
862	11463
863	12680
864	12690
865	12384
866	11275
867	11066
868	12251
869	11722
870	10762
871	9635
872	9162
873	11167
874	11404
875	10657
876	10211
877	9212
878	9393
879	10504
880	10993
881	10319
882	9523
883	9723
884	10788
885	11193
886	12067
887	12644
888	12798
889	11048
890	10151
891	9174
892	8804
893	9221
894	8939
895	8376
896	7804
897	7718
898	8326
899	8706
900	9031
901	9505
902	9585
903	8834
904	8488
905	8899
906	10107
907	9257
908	9217
909	9729
910	11897
911	11567
912	9619
913	8242
914	8126
915	9384
916	9804
917	9731
918	10539
919	10074
920	8914
921	9346
922	9886
923	9041
924	9407
925	10912
926	9719
927	9336
928	8671
929	8619
930	11093
931	9531
932	8212
933	9701
934	9535
935	8065
936	10104
937	10609
938	9100
939	7905
940	7598
941	8913
942	9671
943	9830
944	8865
945	9907
946	9801
947	9010
948	8674
949	8504
950	8734
951	8226
952	8557
953	9620
954	9307
955	8314
956	8813
957	9205
958	9928
959	8629
960	8387
961	9407
962	8280
963	7488
964	8368
965	8193
966	8525
967	8933
968	8628
969	7826
970	7811
971	6980
972	7733
973	8729
974	9566
975	9468
976	10819
977	11300
978	8840
979	7955
980	7591
981	7842
982	7264
983	7043
984	8110
985	8028
986	6305
987	5881
988	8031
989	9249
990	8751
991	7838
992	6335
993	6565
994	6835
995	7548
996	8669
997	7699
998	7571
999	9422
1000	9046
1001	7873
1002	9040
1003	8449
1004	9022
1005	8590
1006	9482
1007	9169
1008	7618
1009	8193
1010	9620
1011	9235
1012	8231
1013	8092
1014	6866
1015	5674
1016	5666
1017	5666
1018	6733
1019	7659
1020	6405
1021	6473
1022	6836
1023	6089
1024	7165