3000
3999 2876 1857 2832 1546 2897 4034 2848 2812 2739 2740 3305 2333 1959 2837 2000 4142 2483 2688 3550 2251 3304 2882 3227 3806 3143 3182 3325 2259 1639 4150 2650 3725 3452 2761 1725 3043 2015 1811 3082 3255 2518 3467 1661 3327 3428 3336 3004 2586 3372 2153 2239 4324 2269 4024 1814 3174 4189 2120 3675 3782 3297 3949 4115 1539 2873 2968 1932 2599 3102 1686 2185 4285 2439 3628 4216 4140 2546 5 1841 3828 1645 2071 1665 4347 3606 1653 3670 1610 3669 3758 1548 2345 3837 2530 4470 1991 2197 3862 4262 2026 3172 4266 3855 4296 2108 4356 3049 3804 4152 2118 3824 2666 3976 4423 3737 2684 1822 3034 1739 4301 2166 4179 4327 2196 2436 2975 2193 2913 4378 4375 2198 3988 2364 3419 3624 3315 1749 2755 2585 2631 2773 1520 4127 4334 1953 4443 2301 3208 4243 2057 2426 2758 4098 4014 4156 2048 4211 2984 2835 2953 2363 3799 1517 2343 3711 3713 1988 1812 2788 1947 3491 4206 4184 2313 3093 3532 2149 3337 2829 3424 3344 2921 4219 1537 2497 2246 4144 4200 1978 3970 3718 2189 4004 1667 3580 2791 4239 2226 1571 3932 3285 2553 2627 3964 500 2587 2776 4000 3948 2462 4487 3545 2883 3812 1916 1849 1914 3395 4430 1825 3790 3205 1719 2034 2738 4081 2825 1783 2914 4042 3250 3002 3119 3084 2995 3746 4295 2584 4241 1928 4112 2669 3320 1839 3406 2475 4368 2915 3719 2216 4047 2404 4212 3281 3197 3548 2745 3422 3759 1897 1526 3328 3073 2600 2591 3269 3519 3877 3858 4313 3038 2524 2466 2380 3655 1629 4444 4462 1896 2472 1794 2032 3128 3732 3920 3339 1800 3132 4169 2770 3210 3793 3705 4141 1588 3353 2893 4453 4236 3704 1960 3859 2620 4022 1677 2521 2576 3817 3368 1801 4118 4059 2498 2519 4178 3626 2559 4033 2541 2641 1838 3403 2288 4318 1652 4078 1727 2316 4077 2134 2644 2898 2954 2598 3940 2438 3010 3945 2093 3995 3472 1762 4173 3836 1982 4161 2875 2171 2174 2359 3154 4346 2675 2091 2729 3402 3348 1847 3581 3189 2095 3235 4373 3478 3990 3521 2917 2564 4137 3416 3020 2942 3284 4306 1659 3466 3622 2870 2887 3724 2260 4374 3262 2086 3917 2895 2324 2104 4343 3569 3123 3967 1603 3090 3727 2697 3568 2853 3214 1944 1821 2657 3239 1701 3480 4480 4349 4245 4013 2264 3901 3142 3991 2526 2107 4339 3757 4220 3952 2447 3400 3342 3203 2386 2402 2136 4436 4135 2783 2860 2366 2451 4317 1771 2391 3267 2276 4275 3140 3323 3068 3259 4330 4040 3423 3499 3750 2579 3042 1721 4107 3389 2206 4171 2370 2621 2236 2721 1981 3880 2050 3598 3923 3098 1649 3936 2130 3014 1599 1504 3500 4350 2244 4175 3800 2985 3133 3818 3772 3805 3145 4064 3011 2090 3994 2397 4094 1634 3751 2279 2952 2299 3603 1994 3397 1750 3441 3294 2659 1602 2977 3963 3607 3295 4369 1743 1535 3560 3448 3265 3109 4008 2608 2330 4252 1793 1791 4122 2926 2037 3287 3653 3444 3960 2581 2266 1685 2562 3199 4293 1585 1778 2572 2900 1541 4148 2532 1580 3922 2652 2470 4113 1967 2626 2340 3409 4023 2212 2336 3897 3313 3985 3312 4062 3035 3029 3459 4167 2511 3435 2307 2617 2719 2861 3847 3885 1518 3032 2344 2683 3525 2939 4300 3126 1807 1542 1805 1961 4225 3928 4104 1730 3192 3884 3715 4475 3169 2230 1684 3371 3641 1540 3060 2132 2767 2415 4424 3933 2017 4070 1998 4474 3947 3551 4106 998 3335 2850 3457 3986 3503 4146 2252 3649 2998 1954 3542 2768 4413 4421 2281 3610 2290 2960 3185 4182 1938 4321 3054 2967 2703 4451 3031 1760 1866 3575 2165 3117 2309 1894 4432 3745 4038 4101 2010 2076 3168 2673 1885 4267 2820 4477 2247 1926 2389 3924 2273 1521 2291 3981 2114 3899 3977 2612 2486 1886 2722 3774 3394 1873 4435 1802 3264 1980 3120 2807 3243 1636 2676 3630 1804 3668 3712 3796 2066 1709 2643 3768 2223 2007 4328 2616 2674 1584 4326 2973 2319 2894 1556 3039 1594 2433 2522 4304 1723 1570 4468 3274 2787 3619 1968 4272 3534 2947 4153 3045 2502 1740 2754 1790 4437 2085 3637 3141 3429 2994 3222 2681 1676 1531 3590 4001 2726 2806 3008 2827 2201 2434 3226 3810 1608 2202 4315 1646 4056 2561 3464 3496 3539 2842 2399 3334 2504 2508 4287 4366 2478 3876 3809 3600 3261 3254 3036 4244 2499 2041 4338 2866 4049 2613 4265 2624 2449 3163 3005 3731 4092 1890 1797 3561 3801 3744 3937 2629 1828 2862 3490 1948 3418 1788 2653 1631 1657 4036 2622 3632 3533 2636 4213 3549 2177 1913 3100 4446 3051 1654 1972 4032 2665 4361 1607 4088 1846 4103 3707 4097 3911 1735 1823 1714 1979 3652 4166 3559 3958 4234 1985 4428 3856 1511 1850 2813 1586 2811 2828 2367 1816 1815 2320 4357 2204 3850 3217 1575 1933 2592 1573 2377 2647 4210 2924 4402 2879 4257 3906 2160 3431 1905 4009 1902 1939 4228 4057 1782 3213 4458 3826 2890 2257 4269 4066 3978 3752 2943 3198 3778 4145 3463 2464 2912 1507 2218 2786 2183 2006 3915 2126 4302 3207 1736 3381 3714 1865 3329 3231 2441 1722 3027 1858 1845 4090 2286 4389 4031 3887 3845 3516 4400 3047 3127 2350 4322 3489 3179 2008 3816 2611 2055 1761 3656 2062 3087 2830 2346 3662 3346 2141 2074 4381 1795 4058 3028 2840 2550 2708 4198 3573 1533 2670 3697 2437 2515 2554 4208 2234 3473 2724 4284 4108 2072 3253 2484 1881 3672 1587 4041 4222 2639 2329 4282 2356 3892 2566 2242 2081 3486 4105 3067 3161 4482 1514 2712 2096 1563 1772 2735 3401 2395 1862 3510 3488 3839 2948 3968 3912 2387 2573 2353 3586 3413 3300 1906 3193 4354 1620 2023 3215 3041 4051 1614 3485 2376 4254 4297 4027 4218 4258 3125 3432 2815 2097 2589 1545 3110 3690 3437 2116 2808 1596 2418 2976 2609 2355 3200 3434 3648 3588 2723 1977 3507 3650 2713 3989 2385 2424 3301 1927 1756 3449 3965 2012 1699 3874 2138 3848 3307 1869 2111 1522 2406 2560 1827 1534 1924 2885 2241 1942 3275 3634 3997 1720 3767 1734 3057 3379 2819 2187 2777 3211 1929 1887 2784 3875 2792 2205 3808 4312 4476 1831 3536 1837 4183 2147 4249 1698 4394 1834 2698 2999 4449 2284 1543 2403 1889 2170 3703 1675 4483 2619 1919 2838 2993 3365 3794 2946 2646 2054 1911 4233 3980 2981 1708 4016 4055 4319 1789 4191 3599 3377 2899 2410 1803 1501 1832 1859 3417 2491 3282 1796 3420 2372 2327 3890 4274 2781 2267 2805 3673 2774 3025 3556 2867 4408 3166 2092 3832 2188 3721 4011 1557 1820 3764 2446 3871 1683 4139 4080 2485 1524 2224 1779 2119 2816 3447 2908 1630 1871 1875 2821 4485 2455 2240 4484 1598 3896 2751 3961 1840 1987 2969 2542 3190 2182 3330 2335 4270 1726 2606 2607 3216 1544 4323 3872 3183 1976 4192 3147 4050 1564 1910 4143 3030 1843 2492 3966 1597 2964 3895 2772 2509 1623 2706 4372 3232 3807 3180 3654 4045 1619 3830 4384 2533 2637 4288 2956 3162 2143 3969 2737 2476 3979 3881 3523 1523 4370 4303 1576 4240 3784 3298 2741 3735 3075 3681 3740 4307 3249 3811 3089 3840 2602 4442 1553 3904 2374 1538 4459 1786 2162 3572 4392 1748 1689 3827 3585 2094 2940 3251 4410 3469 2018 1830 3465 3942 3404 2382 2082 3360 3565 3399 4427 1769 2191 4007 3955 1936 4256 2250 2662 4422 2019 3775 3716 3835 3631 4125 2231 3256 4221 2347 2539 3363 2135 996 2601 2435 4174 4353 2456 3659 3625 4149 3646 2450 1592 3366 2362 1696 4238 2172 1836 2248 1702 3526 2588 4363 2490 1731 2677 3191 2718 1958 2139 4204 2089 1651 1678 4281 2312 2691 3643 4147 1757 3468 3430 2322 2982 2283 3756 4187 1833 2597 3584 1903 3734 3833 2732 4075 2664 2852 1611 1595 2536 3173 3680 3663 3139 3645 4235 1745 2419 1568 3918 3786 2996 4420 4159 4035 3788 3738 4132 2736 3007 2175 2310 3747 4388 4134 3780 2280 2671 1974 1713 1528 4425 3482 2151 4253 3785 3492 4046 3553 2354 2323 3557 3236 3667 4154 2052 2221 2795 2158 4215 2672 3916 3308 3333 3453 3636 2558 2505 2694 2500 4461 1642 1993 1606 2459 4065 3338 3309 2989 4037 1704 2106 2214 3454 1851 3879 3118 3677 3293 2872 2180 4348 3064 2473 2901 4201 3046 2817 4310 2109 2217 3563 3787 3508 1567 2294 3722 4247 3443 2983 1970 3176 2506 1663 3931 1835 2361 2432 3504 3058 3122 2765 3595 2233 2717 2334 2638 1711 2944 3502 3358 1509 4128 1572 4448 3779 1681 3302 2144 1512 4290 4039 3101 2563 4405 3369 3053 3972 1952 4082 2615 2507 3121 2465 4371 2238 3597 3391 2930 4311 4264 1552 4309 2210 2904 2311 1763 3541 4168 1666 2070 3688 2535 2328 3671 1882 3412 1673 3665 4399 2102 3212 3317 1773 2750 1957 3723 2051 4260 3954 2268 1844 2369 2910 3814 2748 3289 3224 3460 3851 2117 3509 2577 4429 3383 3159 3679 4086 2388 2167 3883 3591 3678 2131 3771 2381 3223 2804 1879 4207 3702 4048 3574 3905 4170 2545 3450 1527 3815 3178 3666 3017 2448 3165 3822 2176 1973 2416 2342 3258 4283 3698 2583 2421 3866 1621 2685 2814 3225 1880 1694 3944 3642 2916 3361 2793 2547 1964 4021 1668 3867 1888 3582 1747 1780 3392 3700 3092 4273 4439 1529 3186 3975 2605 2868 3638 2992 2517 4441 4177 3296 4053 2115 1848 3318 4383 2161 4006 3909 2797 3326 1609 1975 1872 3158 1870 1703 2720 2978 2181 2190 1680 3730 3941 2869 3494 2124 2331 2341 1577 3427 3105 1690 2628 1510 2469 2847 1983 3537 2979 3843 1776 3974 3853 2452 1644 2595 1787 3761 3359 2699 2710 1565 2661 1705 1627 3349 2229 3930 1965 2300 2084 1695 2938 1715 3708 1519 2902 1697 2021 3749 3754 1662 4117 1728 4457 3407 4342 3614 4109 1755 3661 3052 3658 1562 3813 2766 3266 2428 1706 3647 4248 2903 2394 2058 4114 2390 2567 2178 4116 2888 3726 3374 2306 4251 2443 4268 3475 3902 3570 1618 2702 3755 1759 4030 3170 2215 2326 2771 3873 2303 3268 1912 2289 2430 4299 3558 1923 1989 2203 1758 3260 3019 3204 3022 4401 3152 4418 2308 4379 2658 3129 3844 3957 4084 2155 2237 3706 1777 2705 4367 1626 3398 1718 1984 3018 2610 2375 3050 2843 3477 1600 1996 2945 3578 4121 2243 4165 4067 2256 2727 1502 2278 2002 3345 3773 4279 2338 4455 4158 2004 2871 3006 2383 2265 2293 2742 3531 1656 4190 1860 1742 3921 2575 2928 2501 1691 3639 3674 3144 1997 3609 2011 1892 2574 4111 2429 3415 3781 2297 2282 3683 4209 2810 3244 2936 2360 2656 3763 3676 4286 4263 3868 2228 4063 3 3471 1808 2038 4340 2696 3476 1505 2988 1971 2061 1710 2668 2249 4463 2016 2020 2423 3242 3497 4018 2314 3271 3164 2796 3846 2060 1768 2457 3685 4454 3602 2025 3234 2747 3108 2980 2103 1931 4095 2065 3621 3701 3983 2660 2778 2063 3982 487 3783 2184 3209 1963 4052 3378 2798 2700 1818 1877 2907 4242 2358 2527 2877 3633 2551 1551 3009 3279 4185 4337 2640 2801 3882 1692 4376 2409 4069 1969 2568 2648 2959 4407 2503 3097 2543 3245 3149 4465 1650 3393 3878 4359 2046 2317 2925 2414 2578 2029 1682 3341 3062 1612 2378 3316 2332 3605 3623 1904 2163 1625 1995 1622 3362 3167 2514 4017 3925 2858 2274 1754 2219 4195 1579 2295 3748 4224 4466 2245 3351 2272 3962 3155 2693 3065 2854 1601 3291 3987 3451 3131 2966 3021 2154 3657 2525 4464 4479 3861 1781 2207 2123 2892 1549 4196 4489 4255 1643 3137 3640 1817 2886 3520 3527 2709 3070 2285 3864 1605 3013 4188 2271 2112 2523 3546 3691 2775 2425 3194 2790 3150 2529 3321 3913 1767 3825 4176 3233 2261 4089 2156 4076 3753 4259 4003 3956 1992 2173 3689 2049 4447 3498 1907 1826 4071 3743 4294 2744 4411 3096 2818 3063 3340 4155 3729 2067 2422 2480 3202 2150 1853 3612 2965 2604 2222 2169 3571 4229 3078 3592 4450 2803 2920 2689 2357 4395 3380 3898 3635 3184 2951 4203 4397 2030 4452 2254 2757 2168 4333 2044 4129 1824 3280 1648 3535 2384 3095 1925 2794 2064 1813 2679 2445 2253 2148 3660 4308 3286 1515 4133 2129 2304 2642 2633 3364 1765 2934 4093 3130 3770 2990 3946 3627 3682 2337 1829 4136 2961 1578 2479 1724 4162 4355 3886 2680 2494 3699 3421 2489 3104 4280 2225 2292 2209 4398 3608 3841 2305 2315 3044 3241 2651 2878 4438 3440 4445 3270 2831 4123 2194 1922 1687 2531 3160 2714 2122 2649 4391 1898 2844 4271 3860 4231 3651 2186 2933 3367 3238 2841 3684 4298 3593 3080 3040 2488 4181 2971 3544 3829 2482 4331 2232 1999 4314 3085 4002 2769 3077 4194 3273 2461 3083 4100 3000 2809 4472 3760 4044 2213 4083 3263 3934 2413 4416 2634 2043 3914 1842 2208 2098 2137 2962 3177 3113 1799 2556 4345 4419 2544 4131 1738 1569 4456 1920 2839 3086 1949 2396 3375 2468 3003 2746 3414 4087 4358 2756 1891 1868 3088 3347 3408 3733 4227 2035 2368 2596 3583 2013 4390 3865 4160 3074 3116 2955 2779 1581 1628 3993 3066 1884 2420 3513 3528 2632 3283 1752 3664 3611 3138 2549 4126 3456 2053 1670 2088 1946 3554 3919 4119 2321 3107 2075 3518 2059 1930 2932 2510 2100 2411 3552 1604 2227 3470 3135 3776 3386 2856 2040 1550 4026 1798 1792 2555 2110 3935 2760 1624 2731 2142 4434 1746 3514 2528 4377 4316 1895 2763 4217 1940 3515 4164 1590 2159 3462 3959 3629 4232 4380 2121 3220 3803 3324 2487 4073 4246 1613 3071 2401 3219 2056 4488 1547 2715 3257 1635 2078 3356 2618 3322 3181 3436 3479 3148 2851 2431 3240 2373 2645 3396 4364 3458 3973 3425 4099 2896 4352 3188 2001 3151 2931 2157 2263 3103 2179 3410 3893 2824 3433 1615 1855 3594 4360 4460 1934 3079 2635 2408 1500 2557 4130 2743 1532 2105 3555 2734 4186 4412 2427 3061 3310 2929 1956 3195 3388 3146 4085 3819 4291 3739 3299 4214 1986 3567 2220 3187 3710 2701 3992 4120 3081 2440 3350 1766 3538 4433 2655 1717 2398 2823 4015 2623 3115 2393 1878 3951 3001 2881 3802 4061 3056 1899 1616 3971 3048 3229 1874 3831 1506 4261 2496 4019 3153 2009 2630 2937 1558 4072 2663 2849 3939 4336 1737 1861 3849 1530 2733 1918 4440 2296 2302 3728 1525 2200 3332 1744 2571 2569 4320 4386 2695 3483 2580 2963 4124 3766 2834 3823 2987 4096 3615 3696 3943 4005 4344 3288 3024 2855 2031 4335 2512 3910 1712 3206 3438 2192 3506 3692 3033 1574 4012 1674 2325 2140 3620 4230 3618 4277 3998 1864 4163 3343 2997 1693 2351 2863 2287 1876 3136 3894 2270 1854 4409 2682 2068 4278 3795 1863 2080 2799 1901 2802 3996 3929 2911 3016 3076 2603 4020 3869 3579 2113 4157 2865 3331 1900 1688 3953 4028 2692 1632 2045 3487 3927 4138 3693 3405 3741 2538 3798 1593 1559 4406 3736 2352 3311 1883 3587 3495 3230 2800 2127 1516 2042 4404 2047 2039 1785 1990 2125 1555 3201 3694 4250 3094 3099 2548 1774 3134 2211 2235 2822 2079 4223 2513 1729 1655 2348 1819 3842 2275 3543 2540 2654 3037 1638 3114 3524 4393 3984 3292 2570 2667 4365 492 2520 3687 4417 2782 2133 3852 4387 2923 4151 3577 3314 1664 2005 1941 3695 2753 3769 2027 3529 3276 4199 2922 3566 1641 2024 2371 3221 2950 2690 2128 3248 2935 2262 2614 3059 4029 2164 4325 4276 1943 2481 3426 3717 4486 1951 3246 2036 2022 3355 2785 3175 2339 2730 3820 2493 4332 2859 4068 2101 3616 2474 2594 4289 2711 4471 2534 3888 3604 1856 2957 3522 1962 3156 1566 3789 2974 1554 2874 2728 2298 2590 1852 2471 2405 2255 3026 3792 1672 3370 4091 3354 2582 1909 4102 1921 3512 3446 3484 1640 4202 3950 4043 3290 3015 3501 3455 3517 2444 3564 3530 3091 3617 4226 1935 4172 3511 4193 3252 2003 3247 3547 2379 1513 2565 3762 3907 3493 2593 2146 2716 1775 3072 2958 3411 2704 4396 3505 3644 2889 2949 2477 2454 3112 3218 2752 3069 2762 2891 3023 1732 2625 3106 3376 1679 2087 3601 2495 1950 1937 2707 3278 2986 1561 2972 1591 3821 1751 2725 3157 2073 1893 1700 3838 2412 2780 3870 4414 2460 3797 3319 4426 4074 2906 4025 2846 2028 2318 2884 3686 4403 2833 3891 4079 4329 3834 3938 2686 2458 3272 4180 2442 1536 3373 30 2014 3442 2083 2749 2 4473 4415 1966 2392 1810 2836 3171 1945 3461 2195 3228 1671 4010 3390 3303 1660 3903 2918 3124 3445 2145 1583 3863 4237 2069 1637 2365 2678 4431 3900 2687 1741 1560 1955 1669 2970 3481 2400 3385 3562 3111 1707 1764 2152 2349 3596 3791 1733 1647 1617 3384 3857 2919 2407 1716 2789 4481 2417 4351 4469 3012 2467 3720 1633 4205 1917 2463 3196 3357 1589 1770 1915 3854 3777 4305 2277 1753 3439 2453 4382 3387 2864 1809 3908 1867 2880 3576 3889 3540 2845 1582 2941 497 4467 2927 4110 2099 1508 4385 3055 4341 3352 4197 2826 2759 2552 2077 2033 2258 2905 2199 3742 3306 3765 4292 3589 1908 2991 3613 1658 1503 2909 2857 2516 4054 4362 3237 3277 4060 3709 4478 2537 3474 1784 1806 3382 2764 3926
min