1	2886
2	2738
3	2439
4	2287
5	2344
6	2358
7	2576
8	2470
9	2669
10	2739
11	2921
12	2885
13	2691
14	2478
15	2588
16	2603
17	2731
18	2675
19	2737
20	2581
21	2406
22	2316
23	2298
24	2261
25	2318
26	2367
27	2259
28	2257
29	1922
30	1661
31	1682
32	1931
33	2048
34	2359
35	2410
36	2343
37	2331
38	2328
39	2585
40	2768
41	2830
42	2822
43	2581
44	2439
45	2352
46	2528
47	2456
48	2690
49	2747
50	2578
51	2576
52	2482
53	2443
54	2370
55	2376
56	2204
57	2324
58	2306
59	2203
60	2415
61	2353
62	2421
63	2440
64	2543
65	2548
66	2465
67	2636
68	2812
69	2809
70	2824
71	2604
72	2431
73	2446
74	2307
75	2367
76	2488
77	2566
78	2930
79	3089
80	3432
81	3409
82	3364
83	3454
84	3154
85	3027
86	2912
87	2729
88	2681
89	2716
90	2809
91	2639
92	2346
93	2186
94	2231
95	2332
96	2401
97	2462
98	2366
99	2283
100	2231
101	2116
102	2345
103	2579
104	2540
105	2425
106	2700
107	2673
108	2533
109	2529
110	2545
111	2818
112	2932
113	2989
114	3027
115	2907
116	2911
117	2745
118	2777
119	2808
120	3087
121	3516
122	3827
123	3880
124	3858
125	3520
126	2997
127	2743
128	2680
129	2626
130	2606
131	2640
132	2356
133	2440
134	2626
135	2690
136	2949
137	3215
138	3215
139	2973
140	2737
141	2343
142	2298
143	2449
144	2554
145	2619
146	2596
147	2636
148	2873
149	2627
150	2485
151	2347
152	2570
153	2500
154	2566
155	2532
156	2289
157	2535
158	2513
159	2428
160	2295
161	2205
162	2084
163	2117
164	2136
165	2223
166	2252
167	2351
168	2406
169	2196
170	2401
171	2133
172	2369
173	2371
174	2490
175	2282
176	2269
177	2421
178	2421
179	2659
180	2509
181	2245
182	2056
183	2190
184	2248
185	2013
186	2012
187	1948
188	2019
189	2149
190	2484
191	2371
192	2457
193	2789
194	3010
195	3152
196	3005
197	2791
198	2470
199	2283
200	2116
201	2265
202	2383
203	2597
204	2651
205	2807
206	2807
207	2593
208	2575
209	2757
210	2768
211	2765
212	2870
213	2721
214	2719
215	2572
216	2557
217	2667
218	2842
219	2899
220	2894
221	2915
222	2963
223	2916
224	2703
225	2849
226	2874
227	2945
228	2805
229	2729
230	2708
231	2766
232	2730
233	2783
234	2290
235	2115
236	1923
237	1865
238	1936
239	1977
240	1761
241	1563
242	1582
243	1571
244	1914
245	2249
246	2720
247	2665
248	2569
249	2283
250	2003
251	2110
252	2341
253	2493
254	2759
255	2886
256	2623
257	2506
258	2657
259	2816
260	2706
261	2659
262	2506
263	2447
264	2298
265	2437
266	2496
267	2303
268	2118
269	2224
270	2507
271	2575
272	2647
273	2447
274	2269
275	1977
276	2068
277	2155
278	2422
279	2634
280	2866
281	2860
282	2914
283	2877
284	2773
285	2731
286	2592
287	2585
288	2582
289	2531
290	2706
291	2776
292	2455
293	2227
294	2252
295	2378
296	2572
297	2390
298	2406
299	2270
300	2401
301	2376
302	2522
303	2558
304	2447
305	2152
306	1970
307	1894
308	1926
309	2121
310	2310
311	2351
312	2351
313	2521
314	2505
315	2454
316	2378
317	2336
318	2265
319	2448
320	2521
321	2484
322	2504
323	2544
324	2696
325	2599
326	2569
327	2449
328	2161
329	2272
330	2482
331	2430
332	2440
333	2444
334	2398
335	2551
336	2524
337	2271
338	2393
339	2392
340	2447
341	2653
342	2553
343	2695
344	2746
345	2955
346	2982
347	2903
348	2659
349	2132
350	1857
351	1513
352	1685
353	1596
354	1902
355	1814
356	2070
357	2279
358	2384
359	2495
360	2525
361	2504
362	2371
363	2144
364	2155
365	2028
366	2292
367	2489
368	2618
369	2654
370	2763
371	2968
372	2925
373	2711
374	2925
375	2766
376	2781
377	2692
378	2589
379	2462
380	2229
381	2079
382	2301
383	2592
384	2570
385	2651
386	2442
387	2326
388	2461
389	2632
390	2613
391	2386
392	2005
393	2083
394	2085
395	2182
396	2233
397	2413
398	2628
399	2969
400	2888
401	2673
402	2296
403	2090
404	2105
405	2476
406	2369
407	2353
408	2579
409	2675
410	2420
411	2210
412	2232
413	2315
414	2455
415	2607
416	2637
417	2587
418	2452
419	2473
420	2839
421	2959
422	3102
423	3267
424	3255
425	3515
426	3285
427	2916
428	2832
429	2876
430	3571
431	3560
432	3234
433	2979
434	2728
435	2588
436	2231
437	2226
438	2464
439	2782
440	2937
441	2711
442	2514
443	2329
444	2307
445	2423
446	2551
447	2554
448	2616
449	2535
450	2368
451	2365
452	2262
453	2235
454	2212
455	2132
456	2309
457	2589
458	3234
459	3217
460	2998
461	2965
462	3009
463	3073
464	2900
465	2873
466	2895
467	2711
468	2548
469	2766
470	2844
471	3156
472	3268
473	3414
474	3325
475	3350
476	3371
477	3030
478	2950
479	3040
480	3301
481	3306
482	3179
483	3099
484	2970
485	3177
486	3093
487	2874
488	2685
489	2419
490	2443
491	2582
492	3010
493	3123
494	3187
495	3522
496	3262
497	2864
498	2788
499	2727
500	2589
501	2551
502	2717
503	2656
504	2459
505	2618
506	2793
507	2992
508	3146
509	3295
510	3471
511	3562
512	3371
513	3680
514	3597
515	3592
516	3691
517	3679
518	3797
519	4018
520	4184
521	3996
522	4148
523	4137
524	3971
525	3482
526	3076
527	2858
528	2871
529	2854
530	3025
531	3380
532	3614
533	4003
534	4184
535	4164
536	4324
537	4409
538	4595
539	4624
540	4253
541	4733
542	4903
543	4706
544	4934
545	4706
546	4283
547	3991
548	3903
549	3825
550	3674
551	3500
552	2957
553	2593
554	2439
555	2838
556	2956
557	3259
558	3505
559	3419
560	3490
561	3547
562	3544
563	3688
564	3606
565	3503
566	3838
567	3750
568	3997
569	4104
570	4352
571	4670
572	4653
573	4490
574	4266
575	4725
576	4856
577	4810
578	4973
579	5472
580	5549
581	5332
582	5379
583	4960
584	4792
585	5087
586	5612
587	5099
588	4344
589	4216
590	4702
591	4605
592	3970
593	3775
594	3740
595	3872
596	3960
597	3552
598	3449
599	3779
600	4156
601	3653
602	3103
603	3091
604	3292
605	3340
606	3324
607	3408
608	3342
609	2966
610	3086
611	2987
612	2764
613	2486
614	2309
615	2331
616	2211
617	2205
618	2325
619	2418
620	2583
621	2976
622	3210
623	2640
624	2328
625	2041
626	2101
627	2019
628	1995
629	1958
630	2162
631	2450
632	2756
633	2504
634	2643
635	2664
636	2422
637	2368
638	2878
639	3554
640	3465
641	3394
642	3180
643	2917
644	2908
645	2909
646	2830
647	2872
648	2899
649	2724
650	2297
651	2493
652	2496
653	2979
654	2918
655	2477
656	2076
657	2040
658	2086
659	2283
660	2334
661	2563
662	2447
663	2083
664	2148
665	2384
666	2376
667	2562
668	2697
669	2854
670	3063
671	2829
672	2249
673	2334
674	2657
675	2877
676	3061
677	2815
678	2371
679	2106
680	1817
681	1574
682	1731
683	2705
684	3286
685	2813
686	2203
687	2371
688	2636
689	2982
690	3214
691	2801
692	2731
693	3265
694	3403
695	3324
696	2780
697	2142
698	2118
699	2377
700	2306
701	2077
702	2370
703	2327
704	2630
705	3195
706	2947
707	2391
708	1829
709	1750
710	1853
711	2290
712	2326
713	2186
714	2296
715	2145
716	2118
717	2400
718	2865
719	3177
720	2990
721	2519
722	2552
723	2320
724	1906
725	1668
726	2080
727	2479
728	2942
729	3092
730	2978
731	2668
732	2357
733	2605
734	2911
735	3321
736	3158
737	2666
738	2529
739	2739
740	2655
741	2407
742	2468
743	2609
744	2537
745	2717
746	2526
747	2477
748	2839
749	3033
750	2877
751	2685
752	2215
753	1713
754	1643
755	2081
756	2194
757	2210
758	2615
759	2675
760	2603
761	2339
762	2116
763	2267
764	2530
765	2450
766	2509
767	2560
768	3032
769	3176
770	3193
771	3046
772	2784
773	2697
774	2426
775	2019
776	2020
777	2019
778	2465
779	2744
780	2699
781	2861
782	2921
783	2610
784	2394
785	2529
786	2288
787	2506
788	2317
789	1913
790	1686
791	2060
792	2377
793	2856
794	3120
795	2762
796	2428
797	2166
798	2512
799	2596
800	2447
801	2501
802	2574
803	2368
804	2564
805	2493
806	2720
807	2402
808	2493
809	2425
810	2393
811	3045
812	3606
813	3292
814	3318
815	3046
816	2668
817	2515
818	2229
819	2180
820	2772
821	2931
822	2971
823	3009
824	2918
825	3107
826	2920
827	2809
828	2845
829	2394
830	2088
831	2274
832	2565
833	2509
834	2291
835	1815
836	1916
837	1936
838	2252
839	2337
840	2491
841	2319
842	2726
843	2566
844	2500
845	2872
846	3212
847	3041
848	2651
849	2791
850	3160
851	3075
852	2195
853	2127
854	2672
855	2191
856	2515
857	2513
858	2529
859	2471
860	2533
861	2274
862	2222
863	2419
864	2293
865	2557
866	3086
867	2947
868	2844
869	2345
870	2333
871	2559
872	2771
873	2382
874	1931
875	2535
876	2741
877	2545
878	2704
879	2989
880	2775
881	2346
882	2293
883	2435
884	2439
885	2833
886	2880
887	2860
888	2592
889	2683
890	2393
891	2156
892	1928
893	1762
894	1981
895	2518
896	3031
897	3220
898	2445
899	2295
900	2524
901	3027
902	3169
903	2571
904	2372
905	2470
906	3245
907	3082
908	2447
909	2370
910	2784
911	2907
912	2127
913	1997
914	2535
915	2711
916	2820
917	2893
918	2833
919	2586
920	2495
921	2316
922	2184
923	3051
924	3176
925	2745
926	2028
927	2272
928	3069
929	3344
930	2653
931	3067
932	3033
933	2776
934	2860
935	2652
936	2266
937	2057
938	2066
939	2468
940	2791
941	2713
942	3328
943	3397
944	3415
945	2962
946	2600
947	3001
948	2540
949	2890
950	3501
951	3486
952	3799
953	4135
954	3973
955	3206
956	3271
957	3382
958	2728
959	2692
960	2946
961	2354
962	2562
963	2509
964	2740
965	2572
966	2795
967	2718
968	2614
969	2921
970	2663
971	2703
972	2938
973	2700
974	2559
975	3079
976	2913
977	2697
978	2563
979	2342
980	2366
981	2568
982	2532
983	2811
984	2654
985	3032
986	2522
987	2675
988	2692
989	2596
990	3171
991	3280
992	2648
993	2478
994	2571
995	2595
996	2859
997	3144
998	3660
999	2838
1000	2203
1001	2895
1002	3253
1003	3110
1004	3013
1005	2357
1006	2737
1007	2989
1008	2710
1009	3230
1010	2976
1011	2959
1012	2859
1013	2808
1014	2764
1015	2638
1016	2566
1017	3092
1018	2891
1019	2210
1020	2366
1021	2326
1022	2291
1023	2721
1024	3061