1	2962
2	3067
3	3417
4	3054
5	2764
6	2598
7	2446
8	2388
9	2560
10	2441
11	2809
12	2817
13	2989
14	3144
15	3225
16	3772
17	4280
18	4348
19	3933
20	3275
21	3161
22	3492
23	3808
24	4454
25	4751
26	4936
27	4314
28	3498
29	2527
30	1991
31	1900
32	1746
33	1510
34	1621
35	1832
36	2139
37	2000
38	1850
39	1465
40	1731
41	2369
42	2718
43	2401
44	1887
45	1374
46	1542
47	1621
48	1851
49	2207
50	2839
51	3607
52	4082
53	4352
54	4092
55	3507
56	2833
57	2412
58	2045
59	2034
60	1997
61	1938
62	1884
63	1953
64	2381
65	2737
66	2733
67	2537
68	1750
69	1406
70	960
71	782
72	903
73	1507
74	2250
75	2974
76	3137
77	2825
78	2651
79	2345
80	2009
81	1670
82	1443
83	1752
84	1798
85	1819
86	2268
87	2717
88	2998
89	2994
90	3264
91	3378
92	3743
93	4059
94	4308
95	4339
96	4504
97	4419
98	3942
99	3193
100	2738
101	2597
102	2672
103	2933
104	3286
105	3346
106	3307
107	3277
108	3039
109	2609
110	1979
111	1668
112	1943
113	2628
114	3498
115	4018
116	4152
117	3893
118	3544
119	2949
120	2349
121	1990
122	2048
123	2287
124	2328
125	2503
126	2837
127	3265
128	3428
129	3085
130	2578
131	2098
132	1913
133	1734
134	1783
135	2023
136	2054
137	2117
138	2215
139	2288
140	2566
141	2818
142	2895
143	2914
144	3072
145	2936
146	2353
147	2048
148	2028
149	2235
150	2834
151	3187
152	3344
153	2596
154	1932
155	1727
156	2330
157	3185
158	3481
159	2876
160	2187
161	1734
162	1982
163	2263
164	2793
165	3131
166	3298
167	3068
168	2538
169	1962
170	1407
171	1214
172	1515
173	2160
174	2655
175	3265
176	3694
177	3774
178	3750
179	3444
180	3127
181	2817
182	2654
183	2926
184	3135
185	3374
186	3400
187	3464
188	3890
189	4070
190	4279
191	4263
192	4103
193	4357
194	4717
195	4777
196	4532
197	4114
198	3499
199	3373
200	3231
201	3502
202	4009
203	4094
204	3599
205	2727
206	2161
207	2069
208	2020
209	2006
210	2434
211	2656
212	3055
213	3399
214	3705
215	4610
216	5441
217	5506
218	5386
219	5059
220	4686
221	4308
222	3644
223	3504
224	3482
225	3640
226	3897
227	3932
228	3738
229	3204
230	3136
231	2783
232	2379
233	2128
234	2202
235	2522
236	2907
237	2965
238	3045
239	3550
240	3922
241	3945
242	3912
243	3714
244	3418
245	3568
246	4181
247	4406
248	4038
249	3081
250	2655
251	2708
252	3081
253	3504
254	3389
255	3581
256	3690
257	3676
258	3328
259	3424
260	3790
261	4701
262	5257
263	5023
264	4361
265	4026
266	3869
267	3905
268	3650
269	3058
270	2668
271	2631
272	2730
273	2721
274	2954
275	3427
276	3821
277	3593
278	2610
279	2142
280	2412
281	2644
282	2638
283	1985
284	2243
285	2384
286	2647
287	2773
288	2676
289	2608
290	2641
291	3163
292	3427
293	3191
294	3073
295	2943
296	2506
297	2005
298	1770
299	1774
300	1793
301	1972
302	1982
303	2060
304	2101
305	2262
306	1856
307	1809
308	2305
309	3200
310	3802
311	3542
312	2604
313	1826
314	1865
315	2646
316	3154
317	3590
318	4002
319	4694
320	4069
321	3217
322	2174
323	2242
324	3008
325	4623
326	6076
327	6587
328	5327
329	3918
330	3046
331	2538
332	2530
333	3291
334	3372
335	3434
336	3593
337	3376
338	2818
339	2343
340	2472
341	2165
342	1942
343	2070
344	2796
345	3741
346	3713
347	3449
348	3388
349	3134
350	2413
351	1327
352	1195
353	1691
354	2525
355	3868
356	4875
357	5424
358	5968
359	5613
360	4180
361	3251
362	3191
363	3692
364	3620
365	3272
366	3197
367	2583
368	2344
369	2852
370	3816
371	5200
372	6037
373	6151
374	5723
375	4921
376	4200
377	3642
378	3245
379	2997
380	3110
381	3517
382	3527
383	3504
384	3457
385	3814
386	4014
387	3795
388	3360
389	2595
390	2345
391	2656
392	3287
393	3674
394	3831
395	4120
396	4001
397	3664
398	3417
399	3421
400	2737
401	1921
402	2211
403	2737
404	2625
405	2459
406	2788
407	3219
408	3256
409	3260
410	3260
411	2851
412	2601
413	3413
414	4669
415	5114
416	4670
417	3342
418	1953
419	2019
420	3145
421	4501
422	4775
423	4340
424	4000
425	4442
426	4670
427	4513
428	4531
429	4748
430	4149
431	2853
432	2597
433	2490
434	2126
435	1698
436	1702
437	2681
438	4575
439	5837
440	5932
441	4737
442	3871
443	3431
444	3662
445	3407
446	2844
447	2893
448	3752
449	4175
450	3725
451	2911
452	2764
453	2663
454	2185
455	2098
456	2216
457	2793
458	3716
459	4388
460	4176
461	3631
462	2918
463	2931
464	3447
465	3756
466	4036
467	4487
468	3701
469	3217
470	2852
471	2818
472	3129
473	3054
474	3287
475	3813
476	4552
477	5200
478	5037
479	3934
480	3214
481	3121
482	3953
483	4351
484	4418
485	4581
486	4824
487	4514
488	3899
489	3197
490	2972
491	3674
492	4551
493	5076
494	5146
495	5367
496	5570
497	5791
498	5921
499	5503
500	5536
501	5196
502	4567
503	4415
504	5512
505	6599
506	7558
507	8188
508	8707
509	8630
510	7770
511	5720
512	4670
513	4942
514	4547
515	3639
516	3284
517	3335
518	3972
519	4655
520	5143
521	5737
522	5274
523	4289
524	4439
525	4396
526	4146
527	4027
528	3856
529	3681
530	3816
531	4617
532	4549
533	3667
534	2774
535	2885
536	3551
537	3920
538	3350
539	2770
540	2804
541	3086
542	3306
543	4187
544	4777
545	4555
546	4537
547	5016
548	4539
549	4425
550	5729
551	7268
552	8086
553	8750
554	8886
555	7037
556	4600
557	3431
558	3292
559	3798
560	4017
561	4192
562	4397
563	4803
564	4099
565	3168
566	2989
567	3563
568	4120
569	4145
570	5206
571	6337
572	5984
573	5096
574	4911
575	4333
576	4284
577	3976
578	4073
579	4805
580	4278
581	3894
582	4549
583	5398
584	6033
585	6854
586	6396
587	6050
588	6371
589	5903
590	4993
591	5184
592	5363
593	5407
594	5676
595	6108
596	6787
597	7584
598	8379
599	7959
600	6788
601	6486
602	6050
603	5239
604	4934
605	6358
606	7678
607	6937
608	5557
609	4642
610	4538
611	4863
612	5690
613	6436
614	7089
615	7307
616	6257
617	6613
618	8054
619	8972
620	8170
621	7202
622	7185
623	6732
624	5861
625	6033
626	7912
627	9296
628	7866
629	5876
630	5441
631	5795
632	4826
633	4162
634	5017
635	6311
636	7037
637	6726
638	6456
639	8336
640	9760
641	8728
642	7322
643	8321
644	10094
645	9965
646	7724
647	5742
648	5637
649	6095
650	6067
651	7231
652	8906
653	8623
654	7882
655	7522
656	6408
657	5949
658	5058
659	4321
660	4310
661	5035
662	5855
663	6029
664	5903
665	5693
666	6500
667	6227
668	6709
669	8210
670	8544
671	9170
672	9997
673	9175
674	8424
675	8527
676	7026
677	5457
678	6772
679	7251
680	5486
681	3925
682	4289
683	5178
684	5589
685	6179
686	6454
687	7210
688	8179
689	7942
690	7341
691	6423
692	5890
693	6872
694	6085
695	6557
696	7652
697	5891
698	4744
699	6027
700	7429
701	8788
702	7826
703	5235
704	4068
705	3918
706	3401
707	3035
708	3945
709	5577
710	6419
711	6266
712	4759
713	4230
714	4583
715	5036
716	4364
717	4545
718	4719
719	4927
720	6535
721	7130
722	5937
723	4358
724	3388
725	3043
726	3059
727	3229
728	3654
729	4049
730	5323
731	6364
732	5011
733	3133
734	2555
735	3799
736	5508
737	8017
738	7325
739	4627
740	3638
741	3560
742	2978
743	3806
744	3910
745	3331
746	3661
747	4037
748	5100
749	6744
750	7094
751	6623
752	6292
753	5339
754	4229
755	4989
756	5136
757	3095
758	2298
759	3747
760	4862
761	5625
762	6143
763	5513
764	4527
765	3535
766	2669
767	3549
768	4995
769	5299
770	4673
771	4496
772	4853
773	5015
774	4928
775	4402
776	3926
777	4439
778	5532
779	6848
780	7502
781	5684
782	6023
783	5866
784	4881
785	5207
786	5576
787	5348
788	4367
789	3126
790	3769
791	4152
792	3558
793	3961
794	3962
795	4151
796	3678
797	2426
798	1885
799	2300
800	1749
801	1191
802	1968
803	2775
804	2293
805	2447
806	2725
807	2978
808	3458
809	3818
810	3040
811	3012
812	2758
813	3394
814	4712
815	4898
816	3779
817	3281
818	4402
819	4701
820	4334
821	3323
822	1874
823	1343
824	1861
825	3230
826	4394
827	5127
828	3389
829	1703
830	1934
831	2957
832	3602
833	3609
834	4801
835	3411
836	2193
837	2008
838	2466
839	3299
840	3951
841	4315
842	3578
843	3549
844	4285
845	2987
846	1501
847	1843
848	3120
849	2743
850	2576
851	2956
852	3187
853	4045
854	3862
855	2621
856	2018
857	2478
858	2127
859	1169
860	716
861	1014
862	2823
863	3532
864	3192
865	4003
866	3515
867	3258
868	2700
869	2943
870	5531
871	6715
872	5796
873	4164
874	2350
875	1810
876	2789
877	2932
878	2797
879	3074
880	3950
881	5600
882	4412
883	2221
884	2504
885	2737
886	2775
887	2534
888	1634
889	685
890	802
891	1869
892	3649
893	3699
894	2179
895	2071
896	2498
897	2343
898	1944
899	1571
900	1672
901	2734
902	3228
903	3612
904	3666
905	2710
906	2504
907	3202
908	2416
909	1750
910	1581
911	1620
912	2719
913	2853
914	1894
915	1610
916	3079
917	3631
918	3371
919	2612
920	2508
921	3321
922	2682
923	5062
924	6495
925	3512
926	2617
927	2834
928	2031
929	1156
930	1946
931	3446
932	2341
933	1760
934	2126
935	1648
936	1277
937	2415
938	3563
939	3373
940	3823
941	2411
942	1547
943	1746
944	1648
945	1247
946	1771
947	2319
948	3330
949	2052
950	1107
951	1670
952	2641
953	2241
954	1336
955	914
956	713
957	1130
958	1463
959	1934
960	3275
961	2300
962	2440
963	3676
964	4283
965	3844
966	3057
967	1974
968	1413
969	1236
970	923
971	1267
972	1547
973	1440
974	2974
975	2158
976	1046
977	1048
978	1718
979	2172
980	2794
981	1830
982	900
983	472
984	336
985	639
986	1055
987	2244
988	3815
989	3614
990	2450
991	1435
992	1148
993	618
994	1122
995	1516
996	2302
997	2867
998	2363
999	3434
1000	3995
1001	2323
1002	3835
1003	4902
1004	5142
1005	3924
1006	2979
1007	2795
1008	2745
1009	1334
1010	2357
1011	3787
1012	2880
1013	1865
1014	2399
1015	2702
1016	1837
1017	1208
1018	2014
1019	2677
1020	2309
1021	1553
1022	860
1023	358
1024	669