1	3159
2	3400
3	3321
4	3304
5	3393
6	3241
7	3601
8	3904
9	4146
10	4116
11	3968
12	3740
13	3744
14	3959
15	3833
16	3687
17	3808
18	4229
19	4778
20	5146
21	5571
22	5800
23	5703
24	5201
25	4709
26	4478
27	4136
28	3868
29	3510
30	3192
31	3474
32	3695
33	3900
34	3916
35	3700
36	3286
37	2785
38	2409
39	2287
40	2255
41	2520
42	2766
43	2692
44	2457
45	2407
46	2635
47	3027
48	2955
49	2736
50	2632
51	2980
52	3206
53	3087
54	2629
55	2202
56	2383
57	3010
58	3534
59	3696
60	3728
61	3922
62	4078
63	4185
64	3577
65	2868
66	2415
67	2222
68	2564
69	2814
70	2961
71	3281
72	3900
73	4666
74	5013
75	5049
76	4759
77	4173
78	3831
79	3664
80	4033
81	4632
82	5664
83	6130
84	6119
85	5501
86	4781
87	3710
88	3048
89	2661
90	3035
91	3569
92	4384
93	5404
94	5956
95	5742
96	5253
97	4800
98	4239
99	3949
100	3915
101	4054
102	3535
103	3241
104	2979
105	3295
106	3702
107	3943
108	3607
109	2950
110	2733
111	2883
112	3296
113	3476
114	4185
115	4561
116	4813
117	4645
118	4515
119	4289
120	3713
121	2807
122	2374
123	2710
124	3451
125	4259
126	4137
127	3494
128	2913
129	2808
130	3162
131	3340
132	3390
133	3467
134	3862
135	4228
136	4777
137	5254
138	5524
139	5408
140	4827
141	4048
142	3680
143	3658
144	3629
145	3721
146	3867
147	3837
148	3542
149	3132
150	2789
151	2970
152	3639
153	4180
154	4050
155	3360
156	3052
157	2770
158	2682
159	2645
160	2671
161	2629
162	2615
163	2664
164	3163
165	3462
166	3869
167	4033
168	4145
169	3986
170	3576
171	2843
172	2947
173	2980
174	2899
175	3081
176	3615
177	3993
178	4246
179	4025
180	3524
181	2727
182	2667
183	2927
184	3153
185	3203
186	3456
187	3462
188	3181
189	3276
190	3562
191	4246
192	4760
193	5022
194	4901
195	4733
196	4122
197	3591
198	3279
199	3165
200	2669
201	2104
202	1928
203	2039
204	2373
205	2780
206	3164
207	3082
208	2901
209	2698
210	2766
211	2962
212	3195
213	4120
214	5118
215	5980
216	6328
217	6130
218	5994
219	5874
220	5465
221	5127
222	4527
223	3966
224	3178
225	2934
226	3289
227	3688
228	4104
229	4700
230	5261
231	4782
232	3884
233	3911
234	4212
235	4030
236	3459
237	3377
238	4119
239	5147
240	5824
241	5852
242	5146
243	4635
244	3864
245	3036
246	2702
247	2793
248	3257
249	3455
250	3515
251	3555
252	3701
253	3608
254	3887
255	4362
256	4926
257	5811
258	7023
259	8233
260	8053
261	7040
262	5610
263	4438
264	3254
265	2935
266	3475
267	3868
268	3846
269	3800
270	3726
271	3913
272	3663
273	3898
274	4357
275	4201
276	3443
277	3438
278	4338
279	4900
280	4436
281	3624
282	3975
283	4526
284	4670
285	4509
286	4511
287	4848
288	4764
289	4223
290	3554
291	3628
292	4311
293	5097
294	5037
295	4280
296	3367
297	2936
298	3116
299	4173
300	4910
301	5220
302	4811
303	4277
304	4096
305	3984
306	3820
307	4093
308	4784
309	5265
310	5657
311	5130
312	4019
313	3295
314	3641
315	4666
316	5150
317	4731
318	3761
319	3461
320	4006
321	4534
322	4192
323	4009
324	5027
325	7258
326	7660
327	6197
328	4279
329	2903
330	2746
331	2996
332	3165
333	3573
334	4560
335	5526
336	5507
337	4412
338	3680
339	3478
340	3717
341	4441
342	5089
343	5287
344	5780
345	7044
346	7828
347	7149
348	5922
349	5494
350	5883
351	6455
352	6436
353	5863
354	5474
355	5059
356	4915
357	4992
358	5032
359	4298
360	3957
361	4239
362	4332
363	4039
364	4598
365	5665
366	6413
367	6193
368	5608
369	5431
370	6300
371	6764
372	6730
373	6013
374	4955
375	3809
376	3236
377	3253
378	3808
379	4267
380	4594
381	4560
382	4472
383	4269
384	3678
385	3583
386	4334
387	4983
388	4700
389	4565
390	5402
391	6663
392	7156
393	7039
394	6598
395	6421
396	5653
397	5083
398	4771
399	4839
400	6049
401	6730
402	6116
403	5105
404	4400
405	3905
406	3618
407	3433
408	3296
409	3329
410	3895
411	4974
412	6444
413	7192
414	6660
415	5551
416	4997
417	5273
418	6363
419	7693
420	7106
421	6013
422	5196
423	5306
424	5584
425	5310
426	5542
427	6435
428	7577
429	7724
430	6973
431	5489
432	5791
433	7179
434	7840
435	7683
436	6546
437	5929
438	6443
439	7352
440	7561
441	7328
442	6939
443	7309
444	7888
445	7485
446	6884
447	7401
448	7883
449	6372
450	4891
451	5032
452	6258
453	7602
454	8166
455	7806
456	6924
457	6253
458	6436
459	7374
460	7527
461	7554
462	7838
463	8104
464	8356
465	7784
466	7029
467	6423
468	6256
469	6302
470	5981
471	6394
472	7106
473	7898
474	8882
475	9155
476	9407
477	9826
478	9858
479	10613
480	11229
481	10888
482	10751
483	10579
484	10167
485	9755
486	10256
487	9960
488	9341
489	9409
490	10395
491	10846
492	10577
493	10275
494	10385
495	10706
496	12109
497	13364
498	14665
499	14821
500	14006
501	12772
502	12537
503	12989
504	12812
505	11162
506	10493
507	10257
508	9107
509	8680
510	9170
511	10130
512	11096
513	12334
514	13444
515	14085
516	13909
517	13801
518	14714
519	15085
520	15244
521	15163
522	15999
523	18047
524	18964
525	18639
526	17850
527	17384
528	18029
529	17598
530	15677
531	14229
532	14291
533	15587
534	16669
535	18859
536	21652
537	22081
538	19969
539	17675
540	17280
541	19933
542	22298
543	22857
544	23064
545	23763
546	24715
547	23225
548	21012
549	22479
550	23729
551	23417
552	24073
553	25665
554	25982
555	24059
556	23380
557	24302
558	22168
559	20260
560	21409
561	23489
562	24859
563	25239
564	25984
565	25008
566	24368
567	23867
568	24028
569	25763
570	29099
571	29686
572	29008
573	31474
574	34370
575	38125
576	41664
577	39358
578	33613
579	30200
580	30115
581	31202
582	36212
583	42693
584	45383
585	47437
586	48358
587	48203
588	48499
589	48558
590	50888
591	54215
592	52848
593	48213
594	46409
595	51466
596	57746
597	57315
598	57381
599	59144
600	61047
601	64553
602	66743
603	65890
604	67659
605	76874
606	84398
607	84478
608	86328
609	91980
610	96040
611	102590
612	111153
613	115169
614	123266
615	125390
616	118474
617	121755
618	133906
619	146286
620	149826
621	150453
622	159039
623	170157
624	175376
625	184670
626	195770
627	201751
628	214164
629	223886
630	231222
631	239074
632	253191
633	263768
634	260107
635	266048
636	287893
637	304518
638	300592
639	286742
640	285606
641	290640
642	289044
643	307900
644	312314
645	301476
646	293371
647	293259
648	307089
649	309750
650	309841
651	316229
652	312981
653	303244
654	306606
655	322247
656	318647
657	309802
658	310738
659	316909
660	315711
661	310087
662	316230
663	315125
664	305489
665	301168
666	305190
667	305136
668	302294
669	292999
670	295477
671	306130
672	302057
673	293984
674	290263
675	275542
676	270719
677	258057
678	236852
679	234844
680	237935
681	225300
682	207110
683	185560
684	167905
685	161017
686	159165
687	159788
688	153356
689	147911
690	141433
691	132146
692	119976
693	112641
694	111498
695	105305
696	96355
697	86929
698	85351
699	83046
700	75293
701	73923
702	75225
703	70595
704	71505
705	69459
706	63200
707	66515
708	66319
709	63169
710	60117
711	60850
712	62866
713	58241
714	51606
715	48885
716	48389
717	43066
718	34931
719	34738
720	40686
721	43199
722	43227
723	40797
724	38999
725	38519
726	37879
727	35721
728	34529
729	34604
730	34846
731	33492
732	33253
733	34497
734	33637
735	34998
736	36834
737	33210
738	27554
739	23459
740	20004
741	19511
742	21901
743	22003
744	19894
745	20263
746	23160
747	23463
748	20062
749	16616
750	16887
751	19580
752	23272
753	25789
754	24332
755	21760
756	19457
757	17108
758	14570
759	13938
760	14283
761	14673
762	16091
763	15324
764	13751
765	13614
766	12602
767	13848
768	15887
769	14123
770	13260
771	11689
772	10524
773	11410
774	13400
775	14696
776	17483
777	18487
778	18240
779	21117
780	22491
781	17366
782	13168
783	13062
784	14509
785	13442
786	12077
787	11513
788	10924
789	11373
790	11113
791	10804
792	10762
793	10420
794	9820
795	8161
796	8583
797	8933
798	9164
799	12113
800	12547
801	11838
802	12202
803	10178
804	7605
805	7372
806	6255
807	4897
808	5692
809	7507
810	10365
811	12190
812	11244
813	10787
814	10698
815	11577
816	11470
817	8639
818	7435
819	9296
820	9294
821	9566
822	10884
823	10399
824	9419
825	10602
826	10629
827	10654
828	9269
829	7881
830	6976
831	5965
832	3801
833	3697
834	6031
835	7797
836	7454
837	7846
838	8514
839	9160
840	7760
841	5315
842	6087
843	7813
844	8281
845	4789
846	3616
847	3224
848	3454
849	5299
850	8045
851	7010
852	6799
853	6238
854	5279
855	6299
856	7055
857	6703
858	7878
859	8230
860	7151
861	5345
862	5129
863	7146
864	7144
865	3940
866	3682
867	5419
868	7366
869	7750
870	7695
871	9750
872	8334
873	6473
874	7320
875	6496
876	6420
877	4081
878	3518
879	3794
880	4104
881	3446
882	3452
883	2881
884	2453
885	4082
886	6305
887	6084
888	5142
889	4983
890	4703
891	3537
892	4040
893	4006
894	4657
895	4843
896	4114
897	4357
898	5393
899	7190
900	6412
901	5369
902	6426
903	7506
904	5793
905	5172
906	5462
907	4658
908	5765
909	6704
910	7340
911	6294
912	5014
913	4550
914	6105
915	5568
916	5169
917	4589
918	4259
919	2870
920	2352
921	3640
922	4879
923	4683
924	3774
925	4231
926	6002
927	6759
928	5280
929	3019
930	2222
931	2865
932	6224
933	7452
934	5386
935	4949
936	5192
937	3936
938	3082
939	4674
940	5566
941	5748
942	5429
943	4864
944	5376
945	5973
946	8190
947	7352
948	9085
949	8850
950	6308
951	5037
952	6552
953	5548
954	6006
955	6447
956	7107
957	6324
958	4071
959	4162
960	4572
961	3498
962	3015
963	2544
964	3256
965	4566
966	4275
967	5082
968	6144
969	4339
970	2364
971	3223
972	3732
973	4077
974	2809
975	3540
976	3977
977	4726
978	3225
979	3817
980	4265
981	2640
982	2371
983	3503
984	2085
985	1447
986	2257
987	3637
988	4913
989	4986
990	7369
991	5896
992	5117
993	3816
994	3066
995	3474
996	2947
997	2796
998	2245
999	2066
1000	3397
1001	2969
1002	2909
1003	3080
1004	3445
1005	6081
1006	7683
1007	7084
1008	6692
1009	5143
1010	4516
1011	3623
1012	3006
1013	2116
1014	3007
1015	3600
1016	4636
1017	4672
1018	3808
1019	1951
1020	1821
1021	1991
1022	2534
1023	4053
1024	4453