1	3796
2	4020
3	4005
4	3470
5	2548
6	2319
7	2613
8	2027
9	2409
10	2278
11	2498
12	2592
13	2972
14	2501
15	3082
16	2744
17	2642
18	2134
19	2294
20	2458
21	2506
22	2398
23	2514
24	2465
25	2376
26	2878
27	2937
28	3052
29	3135
30	3737
31	4493
32	4312
33	4604
34	4653
35	4515
36	4305
37	4119
38	4226
39	4053
40	3557
41	3575
42	3633
43	3552
44	3828
45	3879
46	4017
47	3923
48	4544
49	4377
50	4469
51	4193
52	4192
53	4207
54	3989
55	3849
56	3229
57	3752
58	3658
59	3081
60	3014
61	2495
62	2609
63	3003
64	3599
65	3538
66	3501
67	3502
68	3180
69	2793
70	3282
71	3036
72	3370
73	3816
74	4302
75	4639
76	4563
77	4369
78	3822
79	3655
80	3620
81	3394
82	3851
83	4020
84	4217
85	4130
86	4204
87	3933
88	3861
89	3359
90	3897
91	3551
92	4042
93	4165
94	4312
95	4434
96	4282
97	3960
98	3785
99	3550
100	3473
101	3185
102	3585
103	2823
104	3315
105	2982
106	3365
107	3458
108	3724
109	4159
110	4940
111	4677
112	5260
113	5301
114	4864
115	4967
116	4208
117	3829
118	3325
119	3717
120	3429
121	4045
122	3537
123	3165
124	3222
125	3926
126	4157
127	4659
128	4630
129	4356
130	4072
131	3869
132	4029
133	4193
134	3907
135	3977
136	4059
137	4036
138	4379
139	4031
140	3721
141	3793
142	3491
143	3793
144	4007
145	4082
146	4227
147	5525
148	6113
149	5996
150	5576
151	5057
152	4868
153	4964
154	5409
155	5260
156	4296
157	3476
158	3063
159	2899
160	3428
161	3656
162	3838
163	3433
164	4149
165	3711
166	3481
167	4286
168	4405
169	4768
170	5005
171	4697
172	4103
173	4478
174	4071
175	3468
176	3947
177	3905
178	4187
179	4800
180	5024
181	5161
182	4559
183	4941
184	4728
185	4569
186	4714
187	4553
188	4447
189	4516
190	5415
191	5882
192	6047
193	5476
194	4571
195	3833
196	3196
197	3453
198	3627
199	4105
200	4267
201	4941
202	4465
203	4293
204	4584
205	4802
206	4633
207	5516
208	5675
209	6723
210	5950
211	5559
212	6256
213	6928
214	6119
215	5202
216	4344
217	4289
218	4404
219	4239
220	4508
221	5087
222	6442
223	7091
224	6691
225	6380
226	5406
227	6207
228	5922
229	5738
230	5426
231	5766
232	5724
233	6214
234	6865
235	7017
236	6711
237	6531
238	6130
239	6323
240	6630
241	6553
242	7094
243	5796
244	5476
245	5480
246	6203
247	7184
248	7130
249	6329
250	5889
251	5774
252	6232
253	6784
254	7038
255	7187
256	6907
257	6225
258	6416
259	6750
260	6131
261	5642
262	5268
263	5491
264	5824
265	6130
266	6473
267	6859
268	6647
269	5943
270	5327
271	5768
272	6540
273	6476
274	6095
275	5523
276	5064
277	5319
278	5967
279	6579
280	6904
281	7069
282	7348
283	7921
284	8196
285	7843
286	7696
287	6884
288	6842
289	6579
290	6350
291	7307
292	7555
293	7690
294	7158
295	6282
296	6235
297	6147
298	6519
299	6389
300	6411
301	6575
302	7112
303	7363
304	7199
305	7058
306	7248
307	6812
308	6802
309	8118
310	8039
311	7827
312	6803
313	6701
314	7502
315	8351
316	8525
317	6747
318	6097
319	6060
320	6617
321	7056
322	8008
323	9112
324	9440
325	8265
326	7915
327	7227
328	6946
329	7530
330	8787
331	9128
332	8113
333	8069
334	8498
335	9158
336	9432
337	8783
338	8154
339	7593
340	7441
341	7745
342	8467
343	9365
344	9856
345	10233
346	10351
347	10071
348	8634
349	8198
350	9128
351	10097
352	10730
353	11473
354	10853
355	10749
356	11121
357	12550
358	12138
359	10104
360	8676
361	8261
362	8243
363	8709
364	9320
365	10414
366	11251
367	11921
368	10980
369	10618
370	9944
371	9787
372	10350
373	10968
374	11773
375	11964
376	12013
377	10907
378	10576
379	11484
380	13001
381	14052
382	13626
383	11385
384	10293
385	10096
386	10393
387	9530
388	9264
389	8690
390	8591
391	9198
392	10381
393	11335
394	11109
395	9885
396	9384
397	10217
398	11282
399	12629
400	13196
401	13311
402	12741
403	11938
404	12350
405	12071
406	12246
407	12069
408	12835
409	13425
410	14484
411	15002
412	15551
413	16704
414	17441
415	17666
416	16841
417	15582
418	14125
419	13430
420	13998
421	13875
422	13950
423	13454
424	13802
425	14069
426	15031
427	15937
428	16116
429	15764
430	15849
431	15841
432	15874
433	15770
434	16316
435	16051
436	16157
437	17715
438	19290
439	19557
440	19305
441	18127
442	16969
443	16310
444	17501
445	18491
446	19267
447	19867
448	18810
449	16636
450	14892
451	14552
452	15202
453	16130
454	17402
455	18182
456	18049
457	18416
458	18749
459	19215
460	19579
461	20306
462	19216
463	19013
464	19768
465	20222
466	21784
467	23316
468	23246
469	22716
470	21888
471	21431
472	20600
473	19920
474	20191
475	20738
476	22050
477	23382
478	23733
479	24576
480	24752
481	25442
482	25245
483	24774
484	25820
485	25767
486	23652
487	23509
488	26253
489	28005
490	27701
491	27391
492	26960
493	28486
494	28674
495	28081
496	27362
497	27252
498	26720
499	25859
500	26651
501	28317
502	28622
503	28830
504	27329
505	27048
506	27140
507	27237
508	28938
509	30486
510	32254
511	33071
512	35216
513	35377
514	33034
515	31066
516	31299
517	33753
518	36248
519	35934
520	35375
521	35086
522	35548
523	36990
524	37256
525	37295
526	38408
527	38345
528	38961
529	40149
530	41626
531	42780
532	43728
533	44659
534	44200
535	45494
536	46951
537	45845
538	44679
539	44504
540	45257
541	45987
542	44180
543	42977
544	44480
545	46639
546	46886
547	47704
548	47445
549	47315
550	49964
551	52536
552	53918
553	52796
554	49848
555	49214
556	49756
557	52930
558	53364
559	54121
560	56502
561	57580
562	57281
563	56099
564	56505
565	58806
566	60253
567	60374
568	62082
569	63436
570	65915
571	66218
572	65931
573	64953
574	64301
575	66297
576	67010
577	66159
578	68239
579	71384
580	73301
581	70302
582	67079
583	68615
584	70942
585	69785
586	70795
587	73081
588	74675
589	75636
590	74848
591	73188
592	71193
593	72998
594	74179
595	69767
596	68137
597	67474
598	69610
599	70802
600	68953
601	67068
602	64074
603	64393
604	64522
605	62156
606	63552
607	65845
608	63001
609	59318
610	58568
611	58834
612	58882
613	59591
614	59849
615	60078
616	57116
617	56104
618	55556
619	56257
620	55411
621	53272
622	52853
623	52790
624	51116
625	50706
626	49205
627	47646
628	47559
629	46424
630	44362
631	43815
632	43189
633	43367
634	42984
635	41854
636	40976
637	42176
638	42936
639	42335
640	39238
641	37559
642	38284
643	40903
644	40186
645	36631
646	34786
647	34125
648	36171
649	37291
650	37023
651	35581
652	34499
653	35909
654	38017
655	36919
656	35528
657	37387
658	36111
659	32949
660	31171
661	31759
662	32567
663	31723
664	31209
665	30545
666	30742
667	29113
668	28233
669	27635
670	28516
671	31116
672	32792
673	31995
674	29721
675	26931
676	27337
677	28257
678	27537
679	26083
680	26842
681	27613
682	27736
683	28187
684	25815
685	23525
686	22717
687	24768
688	25827
689	24658
690	23636
691	23855
692	23287
693	23137
694	22866
695	22545
696	23624
697	23711
698	21961
699	21467
700	21657
701	20326
702	19693
703	20438
704	19963
705	19404
706	18548
707	19540
708	20970
709	21142
710	21445
711	20487
712	19368
713	19722
714	20306
715	18452
716	18440
717	18489
718	17878
719	17475
720	17979
721	19170
722	19166
723	17935
724	17788
725	15235
726	14175
727	16218
728	17490
729	18122
730	17436
731	17631
732	17525
733	17350
734	17914
735	19192
736	18518
737	17266
738	16129
739	16172
740	16300
741	16939
742	17306
743	16913
744	16946
745	16351
746	15690
747	16604
748	18036
749	17627
750	16587
751	15767
752	15555
753	16934
754	15803
755	15753
756	14681
757	13602
758	13121
759	14184
760	14894
761	15615
762	14382
763	12831
764	13410
765	13205
766	13064
767	14821
768	14826
769	15258
770	14838
771	14377
772	13032
773	11254
774	10066
775	9744
776	11099
777	11098
778	10656
779	10991
780	11737
781	12329
782	13596
783	13909
784	11628
785	10938
786	12367
787	14277
788	13178
789	12933
790	12296
791	12393
792	12874
793	13072
794	12411
795	11973
796	11999
797	10754
798	9168
799	8806
800	9306
801	9518
802	10058
803	10001
804	9652
805	10112
806	9568
807	9040
808	9435
809	9237
810	9682
811	8723
812	8271
813	8074
814	9186
815	10505
816	9147
817	9524
818	9295
819	10717
820	10727
821	10447
822	9288
823	9286
824	9861
825	11358
826	13069
827	11736
828	10211
829	9816
830	9877
831	10854
832	11669
833	11368
834	10075
835	9647
836	9752
837	9360
838	9269
839	9606
840	9908
841	10818
842	11039
843	9851
844	9380
845	9387
846	8127
847	8740
848	9412
849	8631
850	8170
851	9938
852	11078
853	10541
854	8403
855	6798
856	6046
857	8536
858	8415
859	7214
860	7872
861	8822
862	10047
863	10261
864	8320
865	9035
866	9681
867	7454
868	6906
869	7160
870	7363
871	8014
872	9113
873	8311
874	7694
875	7040
876	6018
877	5715
878	6785
879	7226
880	8388
881	7278
882	7531
883	6441
884	5499
885	5984
886	6366
887	7741
888	7485
889	7624
890	6242
891	5815
892	5398
893	5810
894	7090
895	6773
896	7286
897	6784
898	7851
899	8882
900	7497
901	8215
902	8813
903	7987
904	6734
905	6333
906	7755
907	8503
908	8705
909	7809
910	7093
911	6166
912	5971
913	5805
914	5647
915	5724
916	5056
917	4102
918	5135
919	5850
920	6276
921	6842
922	7168
923	6119
924	5242
925	5834
926	5190
927	4444
928	4160
929	4653
930	5934
931	5138
932	5278
933	7061
934	6905
935	6926
936	5910
937	6401
938	6933
939	7841
940	6668
941	6534
942	6308
943	6735
944	6577
945	6089
946	5506
947	4040
948	4586
949	5541
950	5349
951	5985
952	5369
953	5380
954	5430
955	5187
956	5570
957	3797
958	4284
959	7727
960	8096
961	6083
962	5462
963	6660
964	5552
965	5323
966	5462
967	6467
968	7346
969	6430
970	5387
971	5845
972	5907
973	4401
974	2949
975	3895
976	5922
977	6753
978	6259
979	5697
980	7340
981	7385
982	5086
983	4420
984	4627
985	5088
986	5240
987	5954
988	5770
989	5273
990	4173
991	5702
992	5427
993	5170
994	6923
995	6626
996	7187
997	6429
998	4642
999	4887
1000	5802
1001	5700
1002	6347
1003	5512
1004	4786
1005	5264
1006	5262
1007	4070
1008	4056
1009	3824
1010	4303
1011	4666
1012	5745
1013	5719
1014	5526
1015	5830
1016	6708
1017	6850
1018	6099
1019	6139
1020	4851
1021	4839
1022	5504
1023	5265
1024	5691