1	1953
2	2434
3	2868
4	3044
5	3059
6	3300
7	3662
8	3953
9	3865
10	3810
11	3719
12	3547
13	3579
14	3937
15	4127
16	4329
17	4273
18	4464
19	4696
20	4770
21	5043
22	5542
23	5400
24	4945
25	4266
26	3245
27	2615
28	2040
29	1966
30	2139
31	2821
32	3631
33	4322
34	4750
35	4702
36	4757
37	4974
38	5304
39	5967
40	6021
41	5527
42	4445
43	3244
44	2280
45	2170
46	2249
47	2429
48	2571
49	2914
50	3003
51	3055
52	2896
53	2865
54	3231
55	3255
56	3270
57	3310
58	3342
59	3932
60	4603
61	4921
62	4785
63	4083
64	3147
65	2632
66	2603
67	2544
68	2743
69	2713
70	2839
71	2930
72	3327
73	3407
74	3390
75	3200
76	3116
77	3338
78	3802
79	4196
80	4216
81	4010
82	3933
83	3648
84	3366
85	3152
86	3235
87	3223
88	3420
89	3304
90	3392
91	3615
92	3248
93	3131
94	2852
95	2554
96	2184
97	2147
98	2098
99	2287
100	2346
101	2311
102	2247
103	2755
104	2881
105	2832
106	2682
107	3159
108	3515
109	3583
110	3585
111	3549
112	3803
113	3516
114	3465
115	3620
116	3836
117	4153
118	3844
119	3021
120	2600
121	2406
122	2359
123	2549
124	2650
125	3081
126	3252
127	3256
128	2930
129	2385
130	2100
131	1815
132	2033
133	2300
134	2580
135	2801
136	3292
137	3591
138	3818
139	4074
140	4194
141	4101
142	3434
143	3110
144	2750
145	2858
146	3128
147	3298
148	3048
149	2735
150	2657
151	2626
152	2664
153	3025
154	3736
155	4623
156	5378
157	5288
158	4749
159	3799
160	2966
161	3325
162	4289
163	5124
164	5053
165	4290
166	3476
167	3082
168	3110
169	2960
170	2806
171	2529
172	2877
173	2967
174	2711
175	2382
176	2254
177	2723
178	3449
179	4006
180	4350
181	4844
182	5399
183	5465
184	5048
185	4761
186	4564
187	4217
188	3768
189	3554
190	3295
191	3079
192	3095
193	3592
194	4057
195	4570
196	4496
197	3580
198	2792
199	2343
200	2212
201	2514
202	2495
203	2642
204	2497
205	2304
206	2045
207	1799
208	1810
209	2402
210	3182
211	3996
212	3824
213	3882
214	4012
215	4953
216	5676
217	6204
218	6406
219	6396
220	5892
221	5127
222	4229
223	4603
224	4987
225	5301
226	4854
227	4279
228	3786
229	3794
230	3997
231	4161
232	3812
233	3882
234	3801
235	4131
236	4348
237	4570
238	4500
239	3882
240	3191
241	2772
242	2900
243	3113
244	2780
245	2467
246	2509
247	2831
248	3136
249	2955
250	2478
251	2107
252	2279
253	2716
254	3222
255	3271
256	3014
257	2943
258	3527
259	4597
260	5188
261	5070
262	4040
263	3469
264	3317
265	3199
266	3601
267	4095
268	4403
269	4330
270	3543
271	2838
272	2373
273	2182
274	2562
275	3356
276	3992
277	4533
278	4678
279	4589
280	3974
281	3867
282	4176
283	4769
284	5120
285	4724
286	3940
287	3363
288	3123
289	3588
290	3593
291	3337
292	3068
293	3103
294	3018
295	2637
296	2425
297	2362
298	2623
299	2961
300	3349
301	3633
302	3860
303	4173
304	5016
305	5963
306	6402
307	5341
308	4239
309	3763
310	3667
311	3951
312	4583
313	4851
314	4186
315	3326
316	2669
317	2841
318	3138
319	3926
320	4328
321	3612
322	2801
323	2039
324	1880
325	1825
326	2183
327	2389
328	3344
329	4154
330	4072
331	3249
332	3166
333	3615
334	4191
335	3919
336	3823
337	3659
338	3574
339	3649
340	3792
341	3875
342	4049
343	3994
344	3643
345	3388
346	3974
347	4710
348	4735
349	4738
350	4088
351	3111
352	2205
353	2073
354	2531
355	3004
356	2901
357	2395
358	2605
359	3072
360	3291
361	2994
362	2935
363	2853
364	2680
365	2979
366	3518
367	3377
368	3064
369	3733
370	4700
371	5525
372	5912
373	6118
374	5599
375	4937
376	4621
377	4868
378	5714
379	5824
380	5618
381	5325
382	5855
383	6755
384	7062
385	7024
386	7195
387	7465
388	7153
389	6324
390	5512
391	4541
392	4229
393	4798
394	4752
395	4821
396	5061
397	5578
398	5287
399	4439
400	4215
401	4411
402	4871
403	5171
404	5197
405	5514
406	5585
407	5638
408	6267
409	7336
410	7583
411	6285
412	4565
413	3712
414	4214
415	5031
416	6446
417	7404
418	8233
419	7667
420	5611
421	4379
422	4516
423	5117
424	5436
425	5938
426	5937
427	4740
428	3977
429	4371
430	5839
431	6971
432	6576
433	6038
434	6786
435	8060
436	7753
437	6719
438	5553
439	4432
440	4527
441	5987
442	7965
443	8903
444	9296
445	9407
446	8211
447	5505
448	4251
449	5027
450	6526
451	7953
452	8156
453	7542
454	7271
455	7671
456	7588
457	7055
458	6821
459	6660
460	6991
461	6589
462	5494
463	5577
464	6488
465	7927
466	7880
467	7417
468	6524
469	6282
470	5608
471	5853
472	5851
473	6102
474	6485
475	7111
476	7526
477	7173
478	7908
479	8206
480	7541
481	6895
482	6162
483	5562
484	5193
485	5507
486	7000
487	8915
488	10121
489	9902
490	9095
491	8787
492	8263
493	8261
494	8815
495	9951
496	11944
497	15098
498	17456
499	16181
500	14165
501	12854
502	11349
503	10662
504	11682
505	10570
506	9164
507	9140
508	8781
509	9304
510	10887
511	12763
512	12988
513	13095
514	13063
515	13151
516	14091
517	15066
518	14517
519	13172
520	12810
521	12704
522	12340
523	12808
524	14924
525	16040
526	15863
527	13811
528	12446
529	14233
530	16459
531	17142
532	16510
533	15277
534	13609
535	13791
536	14615
537	15394
538	15276
539	13557
540	13026
541	14159
542	14906
543	15992
544	17668
545	20061
546	20437
547	18307
548	18229
549	19913
550	20150
551	20098
552	21011
553	20061
554	19715
555	21772
556	24785
557	26060
558	24271
559	21876
560	20704
561	22222
562	26652
563	29595
564	29950
565	29515
566	29127
567	29357
568	29092
569	27040
570	26857
571	27398
572	26667
573	26737
574	29000
575	33850
576	39125
577	41869
578	41699
579	39577
580	37236
581	36475
582	36715
583	36152
584	34524
585	35003
586	40323
587	48942
588	52726
589	50576
590	48673
591	49930
592	49547
593	49670
594	52640
595	55839
596	60218
597	63566
598	62986
599	63987
600	65147
601	65652
602	64645
603	68428
604	75859
605	82316
606	87410
607	92215
608	96639
609	102035
610	108077
611	115747
612	122443
613	125442
614	129779
615	137522
616	141411
617	142205
618	145691
619	154488
620	168196
621	180185
622	189590
623	196331
624	205906
625	217389
626	231646
627	246603
628	263767
629	268791
630	276287
631	281725
632	286654
633	306375
634	331484
635	338601
636	335466
637	343632
638	354954
639	360944
640	370513
641	389749
642	390109
643	405636
644	418509
645	417507
646	412077
647	406645
648	416579
649	411683
650	399869
651	382077
652	385763
653	402884
654	393814
655	375426
656	363506
657	366287
658	374955
659	385794
660	392074
661	384124
662	385855
663	392905
664	392776
665	404067
666	424978
667	436177
668	427219
669	414281
670	410638
671	415421
672	429062
673	439231
674	424722
675	397522
676	371912
677	353546
678	345853
679	323672
680	294096
681	261648
682	248752
683	248190
684	231405
685	203539
686	180040
687	168661
688	162696
689	166212
690	158251
691	139388
692	133983
693	134784
694	131304
695	127754
696	123279
697	115854
698	108265
699	95873
700	87764
701	80797
702	76596
703	78051
704	79172
705	75700
706	69898
707	66180
708	62903
709	59060
710	57294
711	57742
712	58369
713	57943
714	52802
715	48405
716	47187
717	47976
718	49043
719	49264
720	48335
721	45342
722	41337
723	39646
724	40409
725	37720
726	35487
727	35256
728	36142
729	35740
730	34062
731	32839
732	30235
733	28782
734	28384
735	28520
736	28705
737	28071
738	25108
739	24845
740	24855
741	22427
742	22413
743	24067
744	23386
745	21456
746	24291
747	25830
748	24125
749	19698
750	18642
751	21078
752	23100
753	24095
754	20978
755	16899
756	15813
757	14562
758	14112
759	15796
760	15838
761	13000
762	14189
763	17246
764	16569
765	14584
766	14104
767	12879
768	14240
769	17525
770	16637
771	14641
772	12734
773	11284
774	11691
775	14879
776	18756
777	19762
778	20887
779	18453
780	14870
781	14392
782	13243
783	12225
784	12059
785	11437
786	11241
787	11113
788	12523
789	12543
790	10013
791	9880
792	9615
793	9849
794	11200
795	12036
796	10453
797	7083
798	7043
799	8633
800	9624
801	10469
802	10614
803	9454
804	7341
805	8581
806	10859
807	9982
808	7457
809	8394
810	9537
811	7226
812	6731
813	7390
814	9588
815	11066
816	10674
817	8748
818	10312
819	12269
820	10951
821	9600
822	7212
823	5581
824	5790
825	6780
826	8606
827	9622
828	8144
829	6819
830	5923
831	6878
832	8021
833	7390
834	7726
835	10055
836	11180
837	10632
838	9469
839	8069
840	5957
841	6840
842	6755
843	5894
844	6056
845	5243
846	4034
847	4365
848	4528
849	4632
850	5406
851	5229
852	5232
853	5170
854	6743
855	6100
856	5202
857	6062
858	6729
859	7201
860	7902
861	7612
862	5758
863	4054
864	3907
865	5074
866	4780
867	4107
868	4346
869	6199
870	7272
871	5364
872	4541
873	5622
874	5366
875	4675
876	6685
877	7796
878	5791
879	4337
880	3813
881	4445
882	5443
883	5391
884	5507
885	4927
886	4742
887	7279
888	7653
889	4663
890	4711
891	4961
892	4422
893	6608
894	8132
895	7317
896	5562
897	4828
898	5285
899	4312
900	5000
901	5656
902	5105
903	5673
904	4640
905	3634
906	4048
907	3546
908	5189
909	5934
910	5258
911	5059
912	7042
913	7810
914	8331
915	5250
916	4107
917	3604
918	4394
919	5531
920	4701
921	3755
922	2442
923	2818
924	3388
925	3799
926	2778
927	2383
928	2803
929	3829
930	4883
931	4638
932	4739
933	5876
934	8674
935	8991
936	6650
937	5458
938	5998
939	7801
940	5573
941	2526
942	2742
943	3595
944	3512
945	3522
946	3372
947	3072
948	4237
949	6171
950	5766
951	5415
952	5233
953	4422
954	2866
955	1607
956	1747
957	2490
958	2045
959	2313
960	4844
961	5522
962	5497
963	4256
964	3148
965	2106
966	2970
967	3698
968	3778
969	3643
970	4181
971	4670
972	5472
973	5938
974	5451
975	4241
976	3201
977	2682
978	1886
979	2113
980	1414
981	1490
982	3906
983	7027
984	6503
985	4665
986	3340
987	3246
988	3062
989	3491
990	2886
991	3326
992	3549
993	2898
994	3281
995	5154
996	4244
997	3793
998	3962
999	3919
1000	2602
1001	2757
1002	2878
1003	2303
1004	1459
1005	1488
1006	1914
1007	2305
1008	3879
1009	3702
1010	3967
1011	5282
1012	3936
1013	2513
1014	2028
1015	3630
1016	2986
1017	1960
1018	1650
1019	1648
1020	3157
1021	3909
1022	2947
1023	2606
1024	2547