g = [4848,653,2856,3641,3271,4609,4387,2211,3537,2415,2049,2571,2877,3588,2002,4488,2086,2795,2880,4000,1341,838,520,478,696,2390,1380,1132,2871,3056,4990,3631,2442,4366,2814,1976,4565,4884,135,2271,3913,1517,4100,2716,3432,2066,1558,4407,1019,3135,4228,195,3936,2569,502,2678,4320,4633,1387,764,3032,1257,1427,24,4286,2425,185,4097,4410,3776,451,4,2205,1216,1839,2789,1609,1332,2843,78,546,1920,3239,1753,2148,558,1648,2269,1561,3591,457,65,38,3030,993,2031,710,680,1253,2578,1898,3923,4039,2777,4161,4456,2944,3238,2067,1174,3993,1245,3721,4680,1311,1375,2234,1964,1572,4174,308,2176,2668,2085,505,2206,3045,3251,4979,3701,5,2162,4489,39,2953,3689,1087,2863,4480,1096,3790,1758,2594,180,233,2546,3333,935,358,243,4421,4652,1414,4482,821,3082,2835,456,2781,1356,3111,1709,1419,2025,1885,1507,4777,1514,424,4079,475,759,938,403,878,1259,2343,1944,3438,1191,1603,1542,618,4836,4462,1887,212,4354,2454,3854,3426,392,3074,3874,2810,2555,3623,4664,1792,1698,3370,1344,455,4058,2386,3038,3585,2217,44,3189,4426,3066,2667,1260,3043,2527,2240,570,4268,2700,4898,892,780,1448,4367,1399,1858,2682,4697,1009,3804,1050,777,204,2839,1351,1919,630,4781,2729,3860,1755,2169,3690,784,3429,2963,3311,1287,4758,4903,2439,1266,3656,2165,1282,3624,834,4033,4812,472,126,2930,3725,4155,3136,4972,156,3629,875,1295,3279,2657,1827,1357,2506,4104,3997,4578,1943,3493,3740,2647,2150,2247,3555,3771,2357,2601,4549,2427,252,1937,2665,319,1659,289,1578,4670,1503,2945,1869,2175,3978,1381,726,2607,1570,3376,4049,437,1250,1747,1855,4183,4636,4403,3148,4397,3185,1779,1263,286,1472,4271,2708,196,4375,1860,1068,4433,700,4253,2596,1533,1911,2532,2249,1912,665,795,4377,298,2913,2489,3039,3265,4815,1095,2984,644,3575,797,310,0,3285,476,1069,3224,3118,1158,312,3377,2630,2272,3435,3059,1407,3276,4611,4681,2664,2082,948,4894,4330,160,1536,3403,3190,3901,76,393,1162,1832,1675,3329,1771,2304,2940,4471,1061,2185,2001,3863,4743,1512,2670,1719,2833,3606,2394,1762,1693,1901,3851,4164,2901,2095,657,2702,1256,4294,3425,1123,2891,3389,4666,2544,1413,2725,4610,1584,221,129,984,2690,2705,531,3203,2320,2334,3146,3625,4084,1878,3486,3748,928,4641,4544,2256,1214,2530,4842,3599,3549,1914,4412,4768,774,4394,4216,449,3269,3261,842,1277,3330,3391,4304,17,701,3401,3697,4529,2735,4813,2710,2845,2434,2005,359,2491,3396,66,743,4938,1331,2844,1851,2130,2960,4619,2199,3105,1025,3497,3466,4886,2181,585,840,1215,3596,2337,4448,3506,908,3159,2688,3604,2853,3950,3550,3742,2147,4522,3603,3885,1422,4072,1834,2101,4766,725,1975,3921,1236,1078,2809,3672,3754,807,4673,3362,1607,3033,1402,4592,1374,2634,4739,4663,2545,2878,567,3331,1141,2015,775,3985,656,4077,1987,150,1166,408,4707,4291,4507,3955,2400,3327,3818,507,4811,805,4217,3833,2788,381,3817,335,445,4732,3857,2125,2335,4706,1870,2168,770,590,1415,2976,572,1629,2416,3931,4486,1369,2675,2462,3734,3933,521,2289,639,3809,3957,3982,728,1921,1998,2859,1248,3154,1041,1418,4965,4075,2561,71,3508,215,3590,4770,452,2924,1479,484,36,1233,4212,1534,4724,599,4927,1587,902,4751,2648,1981,1965,4475,4301,3275,4608,369,4280,4866,557,509,4984,4134,3223,3731,25,2098,2443,4091,2698,635,3988,2568,1645,4632,1186,169,2965,1787,2108,1055,2122,612,3816,3775,2917,490,2474,4555,3287,1866,2058,4030,4413,1103,4992,879,3266,3095,4661,4926,4209,2799,2344,4942,1881,2730,3867,1611,3186,2602,3696,3611,731,2241,4716,3115,2417,964,206,3309,112,1689,682,4146,3183,3760,3695,580,750,2677,3088,2618,860,4912,1574,4511,1820,469,4881,1378,4518,1439,1813,2551,3678,2063,1661,1777,1748,1199,2870,3498,3317,1715,4892,3344,1589,4220,2359,539,2327,4490,4143,1958,2529,2783,145,733,1734,1426,3928,3728,2091,2693,1928,1421,3499,1531,2118,1676,4786,1674,3090,4617,4376,1108,2405,2468,2449,2910,2161,2431,4740,1354,4055,3745,3942,171,547,4659,1591,4350,2105,3202,1550,439,929,1143,2847,1915,2061,1274,434,2509,4701,626,2691,2316,1963,4308,3773,4999,2654,931,4178,1431,4919,4635,1960,3958,223,2378,1516,2283,705,4789,378,610,3099,1182,674,4959,1464,4096,4363,4269,976,1798,4130,259,1417,3849,4364,932,497,2305,4295,4890,3152,2841,2915,2212,4333,3831,54,4821,262,4692,1288,2825,1775,1599,1161,2221,4218,654,416,4830,1089,3875,219,3476,995,1491,3479,228,2867,4107,946,2770,825,3001,3521,1154,3484,3368,3781,2420,2671,4310,4270,4262,2786,2488,631,4180,197,4582,1347,4531,2662,375,1031,2638,4411,1718,1955,806,3919,2516,3335,1527,3393,1113,2989,3991,1678,184,1016,1231,4957,4626,2401,3632,1886,3053,3801,2070,2414,4179,1035,2057,3325,4698,3735,1784,4838,724,2848,583,4855,863,2656,3989,4323,2140,4946,3782,3277,730,4598,1656,1197,2991,571,1515,79,2347,1097,3577,3205,742,3461,4108,1528,1303,3354,1594,4150,985,2591,1681,2353,3016,2590,4040,4839,3057,609,788,1447,2748,3474,1410,2381,4622,1330,1873,362,1112,3027,4941,1424,564,3206,1665,1720,1325,3042,4063,2655,2909,2096,3406,3706,1600,131,1823,3732,3986,869,4837,2738,1706,1302,4353,384,1416,1702,57,603,749,3411,4054,1812,108,2876,1102,1307,960,225,3727,1321,3927,4643,4379,4073,4891,3595,3714,1871,3894,30,2922,4020,2450,793,2440,712,3332,3363,4414,561,720,3788,737,2775,822,769,1815,2032,1716,554,3292,1352,3237,1460,783,317,4035,3981,1264,2324,4593,1312,1582,4093,3460,1368,2621,2995,818,853,10,919,3124,2388,2029,4550,4647,1085,885,2862,1121,3948,3597,2525,926,2920,3168,4774,1099,370,738,3,1942,4195,422,1064,4683,3163,1433,1376,4510,4760,3845,4684,338,444,1907,170,1028,3346,3054,1348,4961,3827,14,2487,2429,1267,4729,4954,361,1897,756,3259,3028,4439,3647,956,4362,504,2696,2890,1127,4450,3581,2921,1060,3992,996,4272,3013,3912,485,3225,4380,4028,800,2651,3541,1843,90,4849,2075,4623,1913,3996,723,901,1729,2908,4590,4498,2364,3640,4276,4136,3538,137,3786,2894,2720,226,4896,3808,213,727,3896,3195,4157,3855,4491,1449,1733,4915,4964,2625,1310,3009,1778,3509,2036,2035,1443,3139,1696,1822,98,1725,3207,3091,3807,1540,4762,3953,3844,4589,328,2358,3584,744,3613,785,707,379,31,3783,4153,2484,3659,2865,2133,3245,2806,373,1631,1100,934,1301,3453,2998,862,884,3554,4634,1210,1795,4757,4893,997,2160,4335,309,2803,3500,1160,3458,2550,2707,4064,1657,4187,3553,1212,855,1712,4586,3489,856,133,1768,4062,4735,2055,950,3084,4975,4118,541,4828,1034,1222,4010,2972,2572,3548,3428,3019,3400,1010,4162,19,2874,179,4485,56,2024,2034,4914,287,2121,4001,3101,1451,2361,4024,2762,343,3188,2575,1268,2717,4560,2864,4546,94,2553,1269,258,4901,949,3571,773,3404,360,4688,257,3227,2549,3677,1722,595,4763,1305,293,3876,2584,3880,703,3068,762,2192,3217,1652,524,4352,4447,3134,3427,4968,989,2943,4102,4869,203,3097,4538,3910,1098,3694,3995,2854,1726,3246,2538,273,1637,2312,1765,640,2306,3785,1196,4967,3208,2172,2467,2992,2861,2663,119,4037,2771,2704,1178,235,3752,1220,1797,3150,3336,1299,4267,4615,1039,1499,799,3255,2128,3254,1129,345,4382,4769,998,2321,1593,2295,1799,2699,4105,3345,2985,2626,2008,4939,2659,246,2556,2897,3116,2113,2533,253,2223,3934,4722,3709,4705,41,1966,492,2967,3318,3530,3947,1071,2230,1149,4922,227,3602,3861,897,2,201,3932,4406,2737,389,142,3418,953,1846,4432,4057,986,684,4461,3736,4240,1202,1573,734,4435,4213,1181,4596,914,1308,2822,2802,977,2925,2297,3085,3240,3838,1389,1837,4186,1817,3525,3546,1547,3886,3905,2323,1200,1566,4604,836,4188,4347,236,4203,4865,4175,2403,4998,676,1774,4602,1738,4715,450,1732,2087,2608,4258,3328,3598,912,2661,503,3777,3517,4665,1764,355,4419,1662,4816,4201,2811,3048,4851,1317,1806,3077,91,2280,4293,1953,2222,4297,1750,1457,4144,3210,3170,189,4759,2941,1137,194,1453,3348,1613,2896,3539,4754,2322,2852,2947,994,1522,2214,894,1469,3970,543,2286,1232,4446,399,2501,4503,911,2892,2194,4163,3579,264,4227,3534,1289,4519,4982,2076,763,2250,50,1442,3440,4080,1217,2518,606,2251,3568,722,2243,459,2384,3350,4288,486,1876,4971,4783,4527,1628,4230,2298,20,3450,1476,4317,1384,3826,480,2793,183,4612,2074,870,111,1249,2229,1848,4895,1838,3711,3058,4631,3192,3583,1462,3094,467,4944,3898,3395,2481,3029,2932,1111,4750,3676,2155,2187,427,1673,896,947,3757,1788,4814,3072,1688,787,4013,3297,2633,3409,877,442,4829,1211,4002,815,1770,3540,4165,481,499,1626,718,2579,1646,584,33,4504,1511,715,2026,2595,4648,3655,874,3235,4986,4655,2123,1179,4244,2437,2637,823,2252,3561,4780,4474,3969,4693,4923,3087,1523,2373,2519,3355,3171,1610,2064,3386,155,16,4314,857,2264,4606,2315,4337,1811,2131,3067,1272,2224,3229,2171,4117,1412,237,3172,1072,2404,597,2452,292,3813,3558,4137,4385,1927,4526,419,3902,3850,1918,786,1686,3300,2045,1487,2782,428,4156,53,1293,4699,978,209,473,4613,446,2823,2459,178,2981,2827,3600,1329,4265,4449,2311,1882,488,3278,2273,1537,2430,4420,3724,4234,1697,265,3286,632,1475,2114,1874,2179,3151,3520,154,3791,888,1577,4554,4355,3653,1118,4575,3065,3197,2582,2395,3634,294,4307,966,3917,2318,827,4741,4226,4646,2329,2893,4283,1463,4564,1849,4004,371,4523,4443,1175,4068,4141,4696,4388,4465,2139,363,4512,4685,239,4019,1052,42,791,3930,2144,3566,4850,4723,4717,2444,589,3011,2469,1012,4172,3310,2929,4219,658,4138,729,3654,2470,1664,2018,3012,2203,2314,1793,139,4567,4088,1152,2237,1397,4989,176,1489,2797,920,1847,1710,2385,3819,1120,3130,1833,1940,540,1456,2069,3182,1875,3873,3234,3213,2038,2363,1530,925,4940,4817,3837,2191,2513,2942,3449,638,2987,1776,4825,468,4065,1339,4470,2541,2369,1004,3903,3282,84,211,2198,2946,1830,354,2332,454,781,945,4431,4398,2531,1644,3664,4238,2510,2495,667,2731,3908,1859,4029,3545,122,2918,3294,2377,105,3935,1821,168,1471,4026,1555,3375,745,2585,4129,1556,300,2712,2056,100,3050,4856,527,768,681,1957,3666,3610,172,1177,2120,4807,2497,652,3879,3156,1405,741,3025,1800,2627,315,3592,4192,812,1841,4584,4749,3536,801,1667,2903,3420,3578,2958,3306,2302,4867,4515,1481,4171,483,4788,4835,2021,218,1641,3882,3044,3869,1910,4668,4587,1632,274,2333,2428,980,188,4289,113,1745,808,4625,972,4847,4858,1861,2348,2836,3469,4672,86,3507,1079,642,4167,4254,4846,2681,2422,2523,1091,591,3312,2387,224,2980,1080,1772,4386,107,425,4334,2227,3413,1569,4223,4348,1495,3770,4113,1865,4041,336,2196,716,2379,4484,2225,650,2116,2900,2733,305,2907,2485,2346,955,3036,2954,4365,4854,858,3564,778,3840,913,2912,318,530,1836,3456,3716,4247,4806,4140,4360,3829,981,2994,3295,623,2902,4810,4408,3228,4650,2916,3232,2391,4047,3128,4753,3888,887,2177,4210,2971,698,1809,1684,4468,581,1612,47,272,4745,2174,3392,3343,2310,2371,3262,2100,1880,2931,817,1192,2255,3759,3967,1093,3679,659,3842,2905,3046,907,1074,2494,1148,3015,1804,2195,83,3384,4883,1978,4514,2238,2842,496,2576,1042,3442,2728,3361,3359,3488,3764,1008,3369,2973,3075,1066,1614,3881,2111,835,465,271,2884,104,3747,276,2436,2099,1605,4702,421,458,2689,2102,1488,4844,2792,1529,159,3236,1714,2375,3107,2752,313,3800,2062,3737,3868,2461,1565,1017,2686,1749,3383,538,4402,45,4135,3778,2146,1204,982,529,4832,2599,3465,1780,525,1128,3382,279,695,1535,1450,4273,3779,1088,1968,3022,4899,3096,2766,380,2408,1630,3794,3121,627,1130,3342,4319,3698,3380,2412,1366,3447,4947,1746,3975,4170,3705,1049,464,1891,3938,2107,2317,4718,4802,873,430,1526,2758,2053,125,3494,1067,1187,4500,4292,4472,3402,556,2492,3319,3862,2715,3744,2816,1,3093,1429,1597,4250,2552,921,1829,2372,2262,3531,534,1271,4521,2210,607,2526,1623,1508,3681,3263,4368,1403,526,1131,4341,3040,2258,1185,3307,4252,4205,1058,820,1239,1474,760,648,4303,4454,1979,2397,3637,2215,2071,3472,4374,3983,3864,1227,1107,4764,4630,1640,1461,4545,303,3915,2711,3528,3638,3618,2926,1682,3645,280,1045,2419,510,1786,2622,2787,516,2642,3431,2977,3562,4284,2887,281,2135,4994,4396,3601,2435,617,4863,3000,3710,1122,2882,2617,2398,3244,248,2451,3274,4963,136,3351,2207,4936,3157,3161,578,2592,2472,365,2039,988,4204,802,2193,4071,1916,2986,4103,2616,4691,3073,4539,438,1169,1685,1251,2421,1962,2236,3964,199,4973,1478,3582,1506,1789,4185,4690,240,2962,4532,3064,506,4547,405,4911,1165,1007,2325,75,4249,3945,245,290,46,1313,4194,3122,2605,3198,74,4417,2961,1201,4202,4597,2392,1176,1134,2886,2888,4229,1794,3974,2072,1653,26,3385,2821,708,4313,52,568,1950,2340,859,889,1168,3303,132,1934,2136,463,2301,4494,2574,3622,4864,3352,4805,3231,1580,3439,2368,3113,4533,1428,3574,2949,3407,3959,3454,688,2170,4645,2757,231,1077,27,2423,2939,3769,4235,326,4945,1452,3683,35,158,2817,3132,3675,4464,3143,3283,391,4773,4929,4159,2360,1082,49,2138,1053,182,3937,3464,690,2017,3211,4541,3821,2957,207,4225,3491,3839,4189,1279,394,3729,2653,4969,4726,4826,3063,2336,1567,3201,629,4208,3780,357,299,4654,3349,2673,3324,4044,2866,660,1585,3692,872,4714,2517,1740,4951,1980,2239,491,3002,1532,4036,563,832,353,4804,3700,4261,1133,4879,905,2244,3906,3884,80,4675,2476,222,4131,2080,4920,596,2732,2772,60,1172,4905,602,683,409,826,302,4988,2760,296,429,2566,1997,4908,968,2382,3296,3399,23,1902,4803,3899,4018,1557,2703,3994,2623,2643,4281,4524,2790,55,1906,2399,3422,3098,2426,3668,4349,1000,3478,1909,1983,4746,2127,2636,2291,2183,4083,3104,871,4493,3252,1647,3726,4809,3526,1872,2955,4005,2914,2970,2296,4346,670,3815,3337,8,4605,4199,2632,4287,4060,3242,190,1371,4917,3267,2460,2969,3193,560,1346,4841,395,164,3006,792,752,151,1946,1548,1335,3501,2307,447,157,2143,2658,4583,4639,2858,1825,93,4981,2115,88,1013,2580,1337,1895,983,1318,284,3738,904,4373,4090,2567,677,4875,1193,3756,2319,3658,3079,1883,2706,2355,2356,2503,4133,939,3060,2050,4797,2535,882,4853,4260,4336,495,3191,1844,4517,3984,2767,4868,4506,29,1228,1437,500,4257,3017,1683,1003,3167,2254,4436,4121,4785,1862,2465,1446,3081,4719,990,1395,435,699,2834,1388,4069,714,2784,181,1904,3177,443,1498,2537,2052,3644,1467,4860,4078,3284,4182,152,4404,4128,651,1554,2978,2993,1562,2471,2486,3519,3979,1982,6,2042,4263,3340,1754,4256,1244,4618,3031,3922,3334,942,3233,4918,366,3512,144,1340,2393,959,2059,3713,1292,1139,881,2380,4207,3338,2044,1116,4725,1322,824,1521,3702,3516,115,4799,1338,2860,3037,3187,4200,406,1252,4115,1283,1298,1170,3646,4211,321,2342,973,2563,1342,268,2796,3799,2496,692,3055,3007,3811,2534,1598,3715,1596,3158,4038,1349,4505,4338,13,2645,3076,1090,641,3470,410,1781,4900,4801,3848,2004,2660,3649,2090,1024,2988,4943,1935,3308,62,4151,2154,4502,3877,2167,3444,4733,1974,2089,3218,4290,2505,2562,337,4149,3795,4676,4034,4101,2274,693,2606,579,794,334,1275,4487,3347,4556,2692,2559,1392,2997,2641,4708,146,1070,895,61,706,397,1595,4120,4614,4196,4243,1890,3357,943,3998,4371,4682,614,4551,4956,924,691,117,2713,1852,1494,4166,1831,3642,4023,2409,4003,2620,4616,368,4255,390,4906,3789,1159,1785,324,2685,4045,3119,628,2351,1625,1757,890,2190,2413,138,4985,685,4076,166,3535,662,1157,1691,2366,4006,238,4009,2846,4424,401,1721,1853,636,1986,1773,1704,3388,81,4215,2245,3164,2749,2433,3305,1842,753,4015,4302,1672,1972,460,3806,1382,3542,2593,933,432,841,1218,3089,2149,4980,1432,1438,4874,1401,4274,2736,3140,2560,4236,2330,11,2948,899,3441,1984,3977,1929,3166,2010,1818,15,1655,4913,1081,3669,2840,2188,910,1766,1819,2432,4771,843,4910,846,2818,2279,2455,906,1509,517,900,2186,241,2938,2341,3120,1189,134,2242,1188,1931,2719,4369,1183,277,2124,220,2267,1001,3614,266,542,3954,4309,3457,1930,3911,2612,1877,234,4142,2226,1230,1695,2764,3437,3972,4720,1180,1225,275,4761,4415,1723,2547,2697,1334,4056,4833,127,4123,1365,177,2990,1952,4158,2778,4278,3495,2014,944,364,3718,1856,2208,3314,3763,2694,1985,4976,1988,1608,3125,1756,2300,4499,1276,1524,1036,1973,285,2614,4017,3381,671,767,1390,2259,3014,4127,2281,1991,210,3103,4574,3114,2650,4008,2479,4877,4937,2047,1744,3092,1125,3021,1970,2536,1455,4790,4479,4599,3524,4109,4305,4214,1173,4279,903,1767,2768,761,3408,1592,1763,4540,1956,1309,4721,2554,4381,1805,3071,4429,3556,3569,1484,2723,593,3691,831,348,3607,3256,577,2807,1430,1396,2755,4193,413,746,4734,1959,4422,2178,4428,3946,1458,1280,3630,2000,331,3371,3378,922,316,3446,3323,3047,3034,2869,2331,2164,3823,1394,1246,2588,1938,4427,2134,4032,4048,1992,3289,4695,1513,4689,3918,1221,3551,747,2669,4686,4222,2714,1905,3360,2586,295,301,4092,1316,1286,2754,1021,2078,1924,2350,377,186,2851,1238,3670,4569,2043,1350,3755,1649,1284,2477,3102,2597,4570,3264,3832,3372,1459,407,1373,2182,740,4563,4344,440,936,2791,250,1663,2934,4987,4535,2927,153,2742,4658,2683,2354,4997,3117,3798,3704,4119,96,3765,1146,1343,1579,4264,1520,1138,4792,1586,1117,4765,813,1237,3951,4834,866,2868,2794,2197,3511,3626,1889,3412,3291,4168,2640,2104,3482,2141,4444,3222,1624,4728,2524,957,3617,247,3176,470,51,1163,621,2740,3925,2313,4184,3110,1700,412,1153,553,344,2041,1583,2156,3272,3621,3723,965,4818,4416,702,1867,3153,2801,2260,1393,3062,3100,1969,2610,3215,704,3513,1358,847,1751,4476,1493,1359,3665,161,3567,2158,4862,3353,4296,4357,4241,4052,951,4843,678,3138,278,845,2268,1315,2117,4173,3322,4457,3141,1627,4453,3200,3463,1868,2982,350,1796,689,1468,3890,3179,4259,2800,3762,669,713,2611,2003,4642,162,1167,3914,2248,3078,4873,576,267,4628,4657,898,4752,766,3971,1671,4358,3194,1355,2376,958,1502,1145,1518,3106,1850,3619,4342,1026,2679,3708,970,4580,1730,1482,4955,1171,3580,4081,2726,1353,3990,4266,4160,3594,519,2157,4232,3061,3123,549,1917,3853,1297,2718,461,2266,2761,4840,1650,3643,270,3147,967,3943,148,2514,2635,58,1485,4566,3685,3515,1434,3687,616,4451,1742,3620,85,3145,4327,4966,2624,3010,2906,3749,4667,3467,2292,329,4787,1814,2968,849,18,2033,1908,1948,850,4520,2722,2744,569,3173,1622,4794,1994,67,4315,1441,1668,3660,4904,1006,2132,1486,1470,4744,1436,1961,3865,1483,1235,4248,3608,261,4573,3787,73,140,147,765,758,4907,522,2743,2983,1854,2463,3766,307,4351,608,891,4070,3587,3281,868,2540,2480,613,1519,4233,2016,1362,2446,3846,3069,545,3941,229,4621,2855,4993,604,2528,3904,3573,4086,4466,1581,2299,3532,1568,3005,3872,3052,4887,3805,1114,4455,1409,1075,1106,3897,4823,1564,3667,937,4991,991,3452,1617,1810,3414,474,975,4674,2759,124,4393,2020,3109,3828,4872,2445,1727,4231,482,3636,4552,3304,1835,4747,2410,1319,3563,814,2338,3847,175,4112,3784,4025,3241,2270,4897,4328,417,804,2838,3761,619,4473,1922,1954,2220,1501,4572,4711,2999,3410,4299,1999,2881,2213,2919,1971,1015,174,4748,2201,4066,1440,2202,4822,3944,4594,4318,3184,2046,4011,3963,1736,3544,1677,3920,2721,4543,2898,1694,4329,533,3468,3671,1601,1404,4713,244,3973,191,2308,3616,3155,4027,2235,1739,383,1423,3162,69,1020,523,4629,1803,3280,4246,3485,4974,1639,4852,487,4601,1497,4528,2521,256,2832,4046,356,851,717,2966,2077,216,3083,3434,1947,414,2604,2054,4730,4437,4478,987,3051,3956,314,48,1386,3070,3514,2747,1538,202,1367,3480,923,1615,130,3674,4931,573,2219,2411,3753,4742,3249,4384,4644,1076,1360,4418,1135,3214,420,304,1791,1190,4600,1270,341,4791,3673,1281,3503,4679,2263,1195,1273,4687,2458,1144,3455,4930,961,4237,2257,2785,4326,2129,349,1896,3772,3397,4082,415,2727,3891,2850,886,4909,2587,837,4316,489,3221,2613,4095,2508,4169,498,4577,830,1046,4949,418,916,4378,1379,3436,4022,3209,1062,3814,2830,2253,4950,2746,2265,3768,3680,2609,637,3160,1731,2504,2936,1370,1669,3926,4483,2649,70,4559,327,3510,3893,3852,3326,4452,4595,3473,2475,514,550,3126,4340,2153,2499,1893,3858,1057,4050,2012,1327,969,242,217,3803,2769,4700,3270,2798,1147,423,3968,3639,1320,2937,1400,3424,3648,462,297,4996,721,4782,121,2674,2979,2558,116,2565,1018,2068,143,3212,3722,2923,1670,4391,232,694,4191,2933,798,586,1643,4372,2006,562,2928,4430,2739,544,433,4074,1636,739,2522,3952,4977,4558,918,3635,2060,1546,2007,2805,2600,3086,1769,3746,2724,214,2815,1059,3836,2106,3260,3243,2819,4042,4649,3366,3733,1094,4831,2598,4198,34,1884,3586,3502,479,754,1466,1314,776,4051,3859,1208,3576,974,4501,664,28,1445,1105,2883,4779,3767,4579,2287,4324,565,4978,2750,325,1903,2027,396,532,4513,2899,1724,1588,123,876,1492,4568,3892,2498,1240,3299,2975,3739,1925,1203,2083,3684,466,3302,3572,2639,2438,4311,77,3448,3543,3390,1278,548,1807,3315,2079,3293,625,4122,2180,4445,1633,400,332,1932,192,4197,2573,1705,2309,1037,2512,3008,1333,3834,288,796,3686,2774,4888,4962,4694,1680,1761,3523,2065,4793,3825,3965,3802,1711,2209,1420,3593,2142,4177,3703,4542,1473,4627,4496,601,2084,1687,1048,1717,4603,3226,3445,1206,582,4469,4409,732,4312,4383,2290,963,404,1101,552,118,1205,2464,4581,1291,2362,4007,1247,323,3612,2964,4800,1255,771,1032,4124,4876,3257,1323,3443,3949,3812,3358,3220,1899,2389,346,3483,2151,2500,2009,320,1056,4458,4509,1620,2326,1454,254,4756,2857,2709,4561,1465,3451,7,3820,2073,2383,2680,1504,1296,3477,1086,655,594,387,4712,382,3365,193,883,2812,2345,1703,1151,2570,3405,3459,2261,3288,3961,3939,2996,4737,4537,952,4021,3883,3379,4516,852,101,2200,809,4827,917,4640,1660,2282,2349,3907,615,4534,3962,1398,3216,2081,3712,4339,163,508,3830,1047,374,187,1241,4395,3751,4181,3758,2687,2734,2684,811,2628,3628,2829,3730,4356,1500,103,3481,587,2339,1525,4110,1336,1923,559,2629,4440,1802,2493,2456,645,711,1104,2695,4508,2407,4778,2233,3887,4932,3133,2542,622,3131,95,1967,1840,672,1328,3796,971,3966,4012,3373,4016,865,4736,1752,4916,4948,63,3268,2374,3559,1728,3835,1863,611,2418,2763,3547,2037,1510,260,1242,2515,3356,3856,1029,1142,2288,2097,1306,1385,1801,2303,1990,605,2396,1621,515,2539,537,3924,999,2828,1845,4924,1888,1666,4125,4677,1444,426,4492,536,1207,4031,600,2895,4620,2119,4738,4710,4928,2352,1619,3533,1425,4703,3180,927,385,513,4525,1743,68,810,2093,3492,1038,2813,3650,3339,1027,4106,3822,3024,3416,592,1894,1391,3605,941,4438,4176,4678,3741,2231,1857,1560,2473,3490,3108,1229,575,402,1155,1690,4370,1541,4154,4148,4553,1022,167,4983,1808,1435,4557,3870,3174,3719,2328,867,3810,2218,1226,4277,2145,782,4880,1790,4331,915,2837,1996,1993,1124,1140,471,3504,4441,4704,4345,200,376,3866,1759,106,3527,673,120,3999,4392,854,2872,1737,205,2745,3652,2483,3750,4497,306,2285,1083,3149,3035,3518,4405,1576,3367,2849,4859,839,3699,2820,2466,3663,4459,3976,2950,848,3522,330,2011,4571,64,4061,251,453,4332,511,1377,1363,3496,3900,1642,4239,12,3419,634,633,1926,992,2615,22,1030,1054,37,333,844,663,4098,4820,2441,2904,4390,828,4638,4325,819,4206,4067,2112,4085,1345,1552,3633,3565,3415,909,3112,2583,1265,624,2294,4111,647,3682,4925,566,1590,535,3320,59,4776,4361,4400,4878,4442,4251,3250,675,1115,2103,1933,2773,2365,643,1826,1073,518,342,3615,2644,1995,2402,4958,3258,3290,1741,3552,803,1634,2013,4669,4637,2589,555,2873,352,2184,1783,1285,1606,3557,1951,4152,1505,4784,2974,2543,372,2448,3871,2019,3960,719,2453,1136,1209,4562,3020,4727,4861,3321,1261,1496,87,4359,4087,398,82,1254,1900,3570,110,21,1638,1065,1539,4795,1110,4808,2088,2166,2246,1044,1406,748,255,1198,512,4624,620,2424,697,3018,3878,4662,2040,930,962,173,4059,1941,2889,1571,1708,2367,2666,4460,1326,3430,940,893,4089,1559,3688,43,1604,102,1194,2652,528,3247,4656,4970,3394,89,2520,2959,4671,230,2490,198,291,1692,3657,772,1324,3387,339,2701,2152,1864,97,3181,4588,4952,2232,3475,2935,4995,3127,4585,1300,386,3693,757,2581,1014,3987,4245,1219,1828,2030,1258,3023,3423,1713,1150,2275,4495,3041,1701,4282,2885,3142,3720,1816,2457,4824,2478,2646,4401,4423,1063,1092,1563,2741,4953,1224,2370,1011,1372,2159,3316,114,709,4536,3421,679,4399,249,4845,2631,1782,72,1545,1040,1602,165,2284,4147,3895,3273,322,1364,4224,1679,3178,1051,149,735,3049,4709,1936,3433,4548,2779,4221,4607,1408,3529,3980,3374,311,3560,3248,1084,598,3916,1490,4960,4043,4857,3793,2406,1543,4321,4285,2228,2875,3129,1879,1109,3824,3589,1005,2293,4389,4298,263,2951,3144,3313,4099,2879,269,3230,1760,1654,4731,2216,1699,282,2023,109,1213,551,3717,4139,4145,4434,3841,1939,3137,2109,861,4653,3940,2511,40,1184,1707,1002,32,3797,501,1126,4425,3505,4053,4576,1480,2952,3003,2173,2804,3175,1977,1949,3462,2092,3487,3417,2676,351,649,4463,1262,4094,646,3301,2028,9,4481,3627,687,4755,4322,588,1544,2502,4889,4467,789,4775,1651,4767,1824,4935,128,2780,954,864,2824,441,3199,2278,4116,4870,1156,1735,141,3889,2189,3080,4902,1223,3707,779,3774,1411,3843,2276,829,1616,2204,3204,4014,1290,4477,1243,2110,3341,1575,4660,1119,1635,3471,2564,4934,92,661,4796,3169,686,4798,1361,3662,880,1618,979,2751,2548,99,2482,493,833,2022,411,1033,4933,3743,1553,790,3364,3253,4772,2911,1989,2808,2603,2776,666,4819,2137,1477,1023,1043,3792,2126,4921,2447,367,668,574,751,2619,816,2094,4242,431,3165,2507,3026,2765,3196,2163,4114,3219,448,340,4871,2831,477,4530,1304,2826,347,1294,3661,1549,4343,2277,4275,283,2051,1234,1383,1658,1551,3398,388,1892,4190,4132,3651,4300,2672,2048,3909,2753,494,4306,736,3609,4651,1164,1945,2756,3298,755,4591,2956,436,3004,4885,208,2557,4126,3929,4882,2577]
A = [2391,1236,4581,202,4793,4413,1312,4189,3891,2009,1607,3219,1232,3537,1823,3003,2738,1244,1597,2719,1600,4080,1108,586,4917,68,3729,2403,553,2911,3086,3416,4266,10,4285,2086,2309,580,1830,1831,4066,2753,4604,1061,3117,2615,1546,3647,1266,2675,4306,366,2837,1037,496,2769,2669,4440,2030,1001,1353,3988,4426,2662,4288,46,2586,771,2458,4398,4361,4072,239,40,4566,3216,3163,4144,3489,1253,4221,416,2983,1972,2576,4178,4166,2032,2157,4864,1962,2423,1900,431,4039,4017,2251,3563,4661,3963,938,4304,565,4353,279,2717,898,242,1053,3626,1281,1668,3243,2658,1815,4010,261,44,3766,2784,4758,283,4476,4247,3879,3217,879,2946,3288,2349,666,3479,337,2944,3721,4172,3588,3398,3103,3018,3319,897,3955,236,3867,3234,3679,2213,3735,1202,2961,1729,685,3077,3381,2367,4114,2575,2254,2797,1731,2158,4433,359,2966,4879,489,107,4052,1821,3201,1780,2735,3788,1892,3027,3196,3324,993,1317,1919,4959,384,2580,4958,1172,2496,3245,4236,402,4534,3541,4923,2730,4030,3059,1185,4956,515,141,4138,1084,1100,962,4346,74,1622,4638,3307,602,3448,1340,35,3992,2799,2363,3894,2393,946,354,836,566,498,632,4750,4600,1064,270,4095,4057,4993,2105,4562,2649,1774,2440,544,2310,361,2388,20,1179,4503,4589,434,4237,4048,4881,30,4847,4806,4134,2292,4800,206,2937,3818,1308,3135,3631,2825,669,2820,1103,4824,3773,3239,4945,4367,4883,4671,4584,4457,3481,277,3864,613,2741,1867,3923,4508,4683,980,341,1634,3028,2316,2100,2190,2033,429,3523,2238,3957,4174,4008,3530,1283,139,3014,3152,2177,2681,3281,1020,1905,3733,3768,3129,273,3845,3385,591,1566,3916,3393,2256,1489,652,3405,334,722,791,1783,1686,2018,2298,329,3330,71,1035,4629,3011,3195,4121,2954,4199,3227,817,275,2589,95,1845,4341,2351,867,4819,880,4616,851,4725,1176,1939,1099,2090,2866,4592,4194,4852,1707,3900,2023,2990,2716,148,4447,4354,1603,4651,970,4845,2605,2325,4944,1404,2057,3860,4230,93,2981,4294,1094,271,3511,4822,1645,2635,3414,1971,2997,473,304,1994,3279,3379,4778,3113,3558,247,4660,110,9,2905,1135,4757,3000,2642,2071,154,3851,2755,2532,899,3517,1716,1508,2873,360,3493,3569,2109,2217,3211,4504,4197,1679,4252,543,931,882,2270,1705,3210,3275,1054,539,583,3436,3790,2555,3167,2492,3404,2089,3316,3158,4404,3817,2412,3843,4234,1857,262,4869,253,4684,80,3592,2173,3800,3608,2794,4071,3528,3121,1637,1180,4650,1715,1089,3446,3472,4799,1304,4491,3256,1406,1007,521,2026,2307,572,937,1855,2927,1095,467,4965,2982,2702,1989,294,1122,3685,3107,1503,689,4390,2084,3320,1732,288,4448,1270,1692,514,4283,960,894,1587,4085,795,3355,1639,1217,2876,523,4809,4090,4913,1348,2012,3017,748,810,743,2438,1944,3610,1229,164,3782,165,2154,3189,3079,2880,50,1311,2068,2917,1995,1042,3361,251,2431,811,1771,2248,2141,2874,3634,1456,227,4940,1013,4086,1860,3961,163,2302,3972,3304,2060,2856,1159,3980,3308,3731,4622,1685,3056,1505,3520,4002,1156,4552,2622,1879,3258,778,2627,4369,4160,3177,319,3889,1081,2994,3921,3749,3600,4101,349,1958,2891,4375,3725,3888,2988,789,2539,4835,511,4242,1873,4479,4469,840,228,75,3300,4055,4371,3013,4554,2103,2877,1832,2958,2485,3929,4911,2184,892,303,2043,830,1160,3465,1979,3351,328,619,2678,661,2663,1164,4338,2245,4176,2176,2559,4889,3178,2853,540,198,2760,1926,254,2002,721,2160,3459,768,769,2253,1670,4916,2199,2550,2204,3586,1931,2506,4557,84,3198,4863,4931,3822,2679,708,860,2471,3457,2209,3865,1440,73,4335,2059,1322,2614,3035,1173,186,4173,4843,3143,2497,3539,25,3966,2870,2808,1374,2700,1543,3247,2065,4127,3621,2282,2829,1737,2685,1083,388,430,852,1545,2097,2381,3061,947,956,1435,58,3339,2828,1323,1810,1250,1024,945,929,4383,4365,2648,3896,1660,3920,4788,4876,2294,3976,4167,1992,1870,3701,3105,3116,2790,3428,4715,2151,1552,442,3949,339,2271,633,2377,4899,972,2267,4438,3065,4422,3549,1019,2516,1416,3373,2285,623,383,2455,355,2207,387,2155,1336,146,414,2453,925,195,908,903,403,3583,4084,1965,4471,4705,2670,3273,3323,2566,1680,2187,4021,683,592,100,1869,3552,1210,2107,1252,4511,1764,1120,877,1928,4224,568,2689,2418,2611,4727,706,1521,3805,3765,3220,3775,3394,1969,1932,31,732,2118,4633,4305,4480,904,2347,2127,2073,2882,773,921,4062,1649,2142,4399,4439,772,546,3958,2567,3125,4435,682,1197,4175,4543,1718,3358,4522,1901,85,4763,4775,345,3833,978,2476,2344,2913,752,3292,157,4168,2791,1344,4663,4828,2164,3759,1555,1119,4526,3215,2369,4902,2936,2358,2443,3347,1984,915,3658,1798,4094,541,503,1642,3857,4838,3947,2291,1619,316,1408,1325,3974,4531,231,393,3371,113,1743,2175,4810,457,3484,872,1060,3543,2916,4582,4572,4103,1191,3271,2910,311,377,3477,4079,343,2513,2654,420,1886,686,1898,3924,622,1938,1535,2972,1118,29,785,98,2479,3078,1417,2964,485,3431,2237,2163,2058,2871,4738,2239,497,1003,3153,3512,2565,2413,3715,4512,2915,859,397,158,1779,705,3255,3742,1163,4206,3090,3111,3451,930,453,3567,2,1957,927,2461,3380,2495,1691,4474,3506,4219,4740,4153,2705,858,2054,982,1807,201,1005,4015,823,183,3748,3690,371,499,4238,4455,1643,4967,1017,1130,2512,1194,788,3939,1812,3794,1057,1050,36,1557,1034,1887,70,3544,1320,1918,4813,3956,4091,1596,318,1627,4025,4713,2801,246,4708,3094,4345,4267,4443,2098,4050,3054,4798,616,3624,1876,3570,2775,3008,47,1613,1853,3884,4235,465,162,735,3166,4520,715,1381,3521,2404,2095,4130,507,526,4,4640,2394,2652,1933,837,4053,4396,2747,1542,3253,967,1091,1880,350,1540,848,2573,4709,2016,3769,3110,105,2518,408,1397,1220,1326,1438,266,3230,3906,1858,2117,4701,2148,2537,2855,3246,653,134,3618,3664,991,3194,4403,2456,4704,1298,4781,3954,2004,45,1522,3048,3813,2803,3184,4641,4141,1199,1806,1059,300,1506,1661,525,3001,1228,284,4907,348,660,4688,2563,1231,1072,4884,2809,2396,3302,4376,2504,2901,4126,3628,883,2619,2348,4487,423,3462,1087,2849,1742,41,4968,1170,610,3525,1092,2266,220,1134,780,1941,3452,4111,4642,1333,2787,1248,322,3965,149,4442,1413,4862,714,965,2379,1190,4789,595,3437,672,4282,233,1102,4076,1187,2139,4897,4772,2993,458,3091,448,2616,1474,624,2959,1745,4350,4645,1443,678,4748,3913,3145,2317,4523,1617,1799,226,3236,4625,1412,4849,676,3031,2225,3377,2001,375,4370,1316,1675,1048,584,1351,2606,2593,136,2313,1242,3427,4986,3092,3944,4553,2483,3513,1165,1990,386,1318,106,4726,3576,237,11,28,2339,3131,1748,4529,2718,1403,1168,1813,1681,806,3391,3209,3471,1841,4626,1039,3069,3397,1513,374,3250,924,2608,1595,2114,1052,4990,1166,2376,2752,1706,1647,2295,2644,1258,716,4326,4187,3265,1903,102,4836,955,49,464,664,2739,1626,285,4459,4019,1455,932,611,875,2666,415,585,2243,590,1460,534,4037,3368,3100,48,3024,2838,550,4339,3672,1454,26,1437,3636,427,1723,214,1427,4606,4612,17,3698,4774,4802,4409,2072,2953,3815,125,4229,152,1906,1981,4357,3922,3997,1011,1485,3455,4951,4932,3533,2653,933,2761,1859,4667,1909,2341,1031,4429,3627,1885,2899,953,346,4210,1935,1803,4073,4535,4301,2592,1510,1514,4386,1526,2478,1599,4360,4840,4888,1633,4182,3676,751,4470,697,245,4045,3872,3240,2374,1973,1961,111,608,4118,3360,3007,443,522,3611,4978,2664,2359,1986,1576,1963,1214,4627,2250,758,3562,3495,306,2029,3224,4110,4744,2771,762,79,2914,551,2843,828,2938,4214,4109,1833,3139,6,4320,3328,2781,557,1982,3996,2472,4074,4089,2088,1653,445,4212,1430,1171,4407,3318,488,4355,4687,4198,394,1593,3223,2726,506,4464,2395,754,3661,4619,992,1257,1934,2789,3940,3019,1346,2205,282,1076,3082,4100,2338,3235,4865,1760,352,2400,2145,4603,3295,2780,1133,3825,3795,1648,1665,3089,4024,2548,2970,2110,628,88,4853,1299,4158,3821,3238,1274,2488,990,2116,3084,1734,4501,2813,614,4652,3704,1893,4368,104,535,2699,665,4620,1032,2974,876,587,3169,4644,3384,2036,1431,4343,1848,1421,3473,3266,2147,4982,885,863,4882,2361,4964,2552,663,4674,268,3970,4686,1405,3881,3453,651,1109,1315,893,1950,4980,1862,1538,524,3514,805,3168,3546,120,4125,2034,2185,1559,1140,2773,1616,1959,3106,3064,324,1470,2296,474,989,2279,4467,3529,2375,380,2680,4672,2694,677,1491,533,3545,4423,4201,3910,2886,494,3021,32,513,4164,3535,1753,662,2087,4152,1988,3183,1006,2079,3681,3625,3905,255,4542,1023,1547,2426,4328,1849,4038,3781,846,4067,2178,1414,1601,1874,4139,4773,3383,1309,2587,775,4149,2821,3365,1592,764,576,4507,4083,4380,1664,2896,2764,1067,532,1377,3482,3343,4078,1401,3989,1930,4222,4340,3890,115,596,2732,3122,2751,1211,509,1080,2598,1369,4596,3114,2920,1730,2934,3809,1286,1512,159,4801,189,917,4613,996,560,4842,2859,188,1758,528,4623,1142,3159,3847,1289,232,259,2551,2765,2111,3073,4519,3786,263,2311,2140,4991,1754,3985,3311,463,793,3193,2562,1904,3547,390,3261,906,2399,42,3097,797,3553,4056,1393,2728,1945,2588,4953,2062,2776,2777,2659,94,2547,4975,3982,3880,4458,2380,3066,4711,3420,1386,1733,4891,276,1113,4489,1588,1998,794,1843,1203,483,2996,2754,1051,2240,1583,3141,2640,4826,4312,3700,1955,3037,3080,1533,694,493,3870,3269,3670,119,3802,808,4742,3208,3172,3590,725,2621,3192,4330,3264,1776,801,1788,4258,2427,961,3326,4500,1532,2134,3433,344,3622,3565,43,4450,4108,1070,1184,2986,1476,2597,2613,2320,1749,3914,305,4769,531,517,4232,3162,4179,3286,1773,351,1719,3925,3519,2061,3907,3596,3020,3693,1018,33,3713,1063,4601,691,4954,4996,3917,4933,648,4943,1667,973,763,1116,2389,2995,516,2197,2798,398,2130,658,564,1519,3313,1735,1529,2373,4029,4049,1230,1395,1293,1800,1946,2015,655,2625,3926,1782,2860,3109,890,2952,727,3406,62,4493,65,1523,3615,3777,4776,2143,2805,571,3369,1763,2875,959,1409,3176,1139,2554,3359,2884,3827,4157,4906,4096,2274,1896,2540,4155,2342,4904,1987,3389,2984,536,77,1297,2230,2193,3401,2501,1611,4475,3999,1272,966,3289,3632,832,1746,2731,172,2494,4926,177,3722,1237,424,3757,1991,466,4059,2236,60,3536,3911,118,3950,3137,129,34,1495,4586,896,4269,3969,3432,3919,2460,736,117,2246,3252,3871,4796,4615,3641,807,3228,4664,4682,1273,1837,313,2327,3364,1929,862,2505,2439,3582,1029,1175,4239,1829,2857,3072,2509,1811,2189,3025,2940,2684,3102,4723,1287,160,4081,3222,3898,3429,192,2392,4278,2943,4618,3497,2912,4706,912,4318,3936,333,4026,1573,1747,4855,3118,1624,3321,2022,3337,1376,3892,4724,4827,4018,988,2748,3829,332,4092,3485,818,977,2419,2655,199,1631,4783,409,4895,4145,3157,4867,4761,3254,2571,3984,1638,3375,3730,2816,1473,3350,1387,3854,1875,4524,4035,2521,1953,2671,784,4472,4577,450,1022,3677,2720,3678,2233,4389,1149,4545,1883,1338,2407,500,4973,4402,3589,3564,1602,4530,4548,1980,821,2734,3998,3938,219,2465,3297,3026,1960,406,1123,3413,4936,1777,561,323,230,4657,1245,2749,1182,4877,3312,3093,4260,3447,317,1850,1375,4270,3798,3357,3283,302,4807,770,4028,3663,2259,4702,3004,2926,4418,2933,147,4825,916,3423,2475,1107,4240,3705,2037,4675,4666,4377,2229,3165,4209,4325,555,83,2709,4637,2276,1352,1966,519,2211,1560,3585,3751,854,1509,4925,207,4812,477,4941,3653,447,2150,4506,1854,783,1751,3869,4131,2324,1475,274,1581,3714,1097,1794,3409,612,2560,4140,1713,114,1698,4468,2168,4243,2241,1196,1913,4366,4656,2729,1280,3928,476,723,998,101,724,4014,1152,4392,2620,2490,2939,469,23,3186,53,412,1451,3662,911,2498,3838,3962,873,650,2200,1399,126,3491,3237,116,1262,4287,3803,212,4058,2227,91,2998,2371,4814,3859,3047,2120,3660,3885,1676,3099,1328,326,2293,3370,3557,2224,462,4000,3603,4505,265,3846,2631,2203,425,518,3310,358,4156,729,2469,4741,913,2434,19,131,209,459,1471,1390,4097,3609,433,2962,926,2188,4927,1462,4031,1936,92,2691,200,3396,1445,2973,370,3034,4632,2903,4957,3212,2594,856,4136,3804,2242,4431,4416,244,4420,4804,3175,413,1486,1,2231,1324,4786,1419,1354,3581,4434,710,3556,2951,2858,4040,1082,3229,4246,256,4665,4488,4075,3408,1449,3727,593,1518,3207,4013,3959,3762,1093,4992,3606,2812,3620,826,12,871,1809,1695,1511,1610,4719,3067,4634,1026,3858,2119,2278,13,1457,744,4995,4597,4930,4759,4559,1364,1332,3259,1213,976,2832,2076,3419,264,3164,1027,944,1251,1666,4410,140,3490,589,2415,2851,819,1049,1188,4859,2822,2459,1922,2647,1360,3652,4563,1591,4213,1442,4751,1796,3045,2357,4093,2836,2191,767,4203,1014,3301,3811,2596,3952,827,1558,3744,3203,363,3504,4104,702,4914,2928,4752,4364,3434,2208,2430,3483,2083,1612,4016,2261,2634,2529,579,3475,4428,4379,4397,637,2397,3180,559,1264,4692,3584,2895,3242,2332,2329,1086,1147,760,4610,1768,574,2132,1125,4621,4808,2861,700,3778,1071,1663,1127,1861,4393,3527,3411,2522,63,1881,776,181,1484,3946,4994,1267,258,1590,1781,3942,4250,16,2744,156,3883,3516,2617,372,3619,3791,4922,1669,325,1689,3421,582,3930,2574,1000,755,81,2502,1498,2378,2121,4292,2235,4482,3684,194,422,3005,3244,4186,193,3232,4502,615,452,3088,3741,2452,4901,2206,4837,2535,2425,3146,4971,1650,1805,1246,2534,1629,484,3458,2353,3231,588,2766,2186,578,1465,2657,1785,2907,4322,4347,3951,4154,1085,779,4829,1598,720,2833,2000,1516,1884,2405,4735,1428,3296,3836,4648,4765,3188,327,3650,2545,3474,222,223,1983,2819,405,57,2019,3671,2600,1420,2723,4866,4861,1844,505,1565,2584,1580,3932,2807,4451,4974,3442,2844,2553,1079,3912,1238,418,3638,3205,3895,3187,4436,1895,1789,2268,4782,175,243,4146,1110,4912,3964,2503,4497,618,1056,3249,1434,1265,3081,4564,2447,66,4585,1921,309,1016,3717,3500,1720,790,2865,3776,4550,170,3823,728,844,182,1363,835,3893,4200,886,2021,730,1902,1769,950,1976,4098,3095,4248,3747,1537,4068,39,1155,1632,1564,3644,2013,142,562,1295,3878,2159,1041,3002,1144,428,4938,3133,813,3480,1008,3322,3101,4509,2977,491,4537,0,3221,435,4714,1644,4077,1398,4259,4846,3550,292,1820,2827,4202,4462,2636,3460,4928,1208,3449,4787,3508,4359,640,3341,3392,3382,299,1694,4691,4432,3780,1319,3824,2328,4915,2796,78,1492,2690,1062,3467,1911,3607,812,364,4205,234,4575,421,1496,1331,1461,2063,2774,733,4753,2942,2252,4162,968,1292,815,3349,2113,2890,2569,1305,1977,2623,1392,4245,2673,218,699,2971,3190,1391,14,2275,928,2053,1225,4587,2762,3486,342,734,1058,1458,1396,2125,3764,3023,1334,2707,527,1112,910,3439,2091,1838,187,4803,680,1697,1826,2854,4225,1726,2639,3199,1204,820,260,4950,984,2835,4955,2281,4099,3990,3599,4128,1268,3746,3960,2672,556,1520,1143,2343,4298,1300,1494,1247,3074,2174,1609,1577,1015,4151,3325,461,224,1942,1978,1693,1536,1699,4020,4112,704,2011,3456,2223,21,178,2651,3218,3006,8,4785,4296,1924,121,1673,3206,4903,3202,855,3327,376,2830,3353,2064,1725,1795,542,907,480,210,3058,4483,1078,4717,4417,314,3123,3,4762,4816,1866,1425,1479,1313,2786,3578,4669,2457,3774,1836,638,3510,4532,4184,2746,905,2887,3515,690,3771,2957,3492,2514,4659,471,2123,401,2632,644,4419,1717,2181,4697,213,3315,1478,2637,3575,824,4477,2919,1872,1137,1548,3739,169,1952,208,2433,2878,4391,3902,2989,4574,3723,1569,4449,2696,3124,4983,2290,1739,2044,1321,4817,1366,1727,598,2991,750,1241,400,4594,2165,1500,1641,287,3151,1927,4430,4693,3830,3561,4873,2908,4193,4323,3272,1117,4044,2138,1967,4830,1030,1970,1365,2893,2533,1562,1897,850,2733,1226,887,2170,3937,954,1658,4465,440,1275,2583,4890,3559,4754,3299,2924,3709,4254,1525,4643,2247,2779,417,353,1368,4481,3580,2960,948,2845,1940,2055,2814,4768,4946,1750,981,2334,3033,2312,681,1825,2435,3280,4811,1839,1154,2115,1594,3683,942,868,4180,3832,1284,2864,803,1452,1450,3469,1277,1055,4337,2692,2641,2442,3605,1671,3112,1178,4142,3793,112,203,2047,4415,1882,4887,4513,4694,874,1477,4710,1801,3400,82,2144,4069,4352,4963,625,1786,1138,2676,1487,1271,1554,362,444,1407,4119,3287,2727,4721,1708,2318,3994,3478,2894,2852,2345,2737,1433,4273,1899,1640,3010,2546,2782,1968,3695,1111,1651,315,487,4117,3499,1620,2817,356,4654,291,3412,1227,958,2402,4979,3334,1021,2153,4777,1380,151,1615,1379,1121,3841,3050,1157,4348,2082,845,4549,4734,2527,1738,4461,4034,4170,3716,1623,69,688,3635,4624,838,1586,1301,367,3694,373,2638,1714,2444,3532,2947,4394,1004,1356,2124,2280,4609,4276,382,3262,4815,446,2999,3053,1146,3738,4791,3138,3036,2222,2955,2561,4009,4314,4712,3354,4780,1355,3816,1215,2630,2950,4384,99,2340,1347,4233,1625,741,204,1502,1490,2898,2039,27,3572,4595,3154,3204,4211,1949,4220,3728,4794,1888,3267,441,2474,1846,3277,2688,777,2687,4362,1362,4047,3161,2628,1915,3542,2169,4424,3466,2277,217,338,2520,3983,2129,1394,3779,4135,671,4023,1209,184,2811,1621,2578,3155,2096,2066,4614,1816,4064,3868,718,3487,668,1589,2847,3656,235,861,2027,2337,2255,4295,3181,2923,1129,1539,631,3642,1654,3897,4268,3470,2314,4832,2579,570,3022,3909,2743,1269,567,2075,2772,1530,4987,4909,2401,1515,335,2480,4602,2591,2283,3736,1851,2390,888,1575,4116,520,2232,392,4743,742,3568,3136,2410,238,1701,4567,1657,87,1115,2682,250,3104,2102,4228,4918,2881,3801,4977,985,475,2831,4677,3842,357,4310,1472,3108,1531,3918,4327,712,4165,3225,2802,1415,4997,3848,4851,3372,307,145,1150,3029,4223,1426,2963,1065,4872,2135,4006,1098,2536,320,4653,4736,3147,4770,2287,1608,1704,4065,1370,2626,4590,1302,597,4196,3931,4698,696,211,2660,552,3503,381,3395,4226,4540,3633,3306,2422,2384,3012,849,4324,3030,3555,1077,3374,3130,1842,269,2024,1551,4679,3706,2976,4924,1889,3783,1342,4858,2511,2818,3282,3403,636,2624,1741,3418,746,2629,2356,4293,2014,248,3934,330,1468,1255,3986,4576,2322,3645,2493,3752,4183,4737,4533,4427,4658,2582,2262,1678,3399,4722,2968,979,37,2051,2215,4908,1499,713,3761,4538,1920,4485,2846,1817,2668,1169,2437,1350,205,2210,2618,2192,558,3756,4756,3039,4148,693,4495,2543,3340,2840,2462,3814,3987,3329,3591,2810,135,59,196,4636,215,1383,1871,918,4988,3507,4670,3785,3643,229,4277,940,645,4518,599,103,501,798,289,3835,3812,3655,2017,3853,486,456,1467,1614,603,922,2918,1285,1483,2273,4192,2162,4027,3703,3126,4573,1964,969,1517,2289,3450,1635,4120,3132,3171,3882,4336,2508,1359,4441,155,2411,4046,4784,1630,2948,72,385,3278,957,3430,2525,123,4797,2265,3680,4265,4356,308,2740,3200,4257,2841,3899,2595,3855,2052,492,4460,3366,2538,2945,3294,2722,4412,2932,1261,629,569,4251,2904,1223,1752,765,2228,1441,127,1410,2978,4937,1466,4823,2607,3335,2601,4401,3993,3719,3016,4275,4668,2010,150,1200,4241,4948,1263,2352,1349,2661,3604,4760,2889,1778,3772,3755,2603,4551,4492,575,1177,4453,4844,1276,1954,2244,4473,3518,368,3390,738,455,4087,3623,3668,2869,1488,2785,3468,621,1578,2721,2921,15,3648,974,1002,1541,1937,4960,4525,2092,2099,1310,1504,76,4437,1974,109,4317,4107,2604,86,4591,1388,4966,1282,4262,389,3150,4875,2656,4558,3887,4970,1009,1358,2568,3173,1151,2166,3659,3601,829,3797,1221,4281,1856,2146,1688,2028,281,604,1724,4539,2667,3820,2883,122,3754,857,4274,2885,786,293,1145,1254,321,2481,2221,2524,4695,3331,1567,1345,1907,185,4593,2800,3874,878,137,3042,4976,1767,1696,600,3973,4848,620,3720,554,4766,4042,529,889,1124,4227,1167,1025,4043,1411,3149,1045,1432,1385,4935,548,3338,766,2214,839,4746,252,167,3612,296,3087,3784,1222,1917,4374,4159,2975,4920,2758,1996,1770,711,3422,2336,757,2198,3387,994,3767,3808,2085,865,3876,4792,3726,606,809,2070,891,4256,1201,4989,4515,1357,549,508,144,4885,3953,4321,1711,4898,143,834,2362,4764,436,1822,1951,3745,2683,2507,1975,3696,2288,2542,2467,1028,2710,3901,804,3276,1999,410,3540,3270,2025,695,3686,4088,642,941,1584,1073,280,3673,3573,2879,3424,934,4747,866,1192,781,753,1852,2301,1762,3657,2706,479,4984,1224,1341,1772,4022,3062,3425,4003,761,1216,4510,2450,3524,617,1219,2941,4517,643,2297,2284,1422,1572,1278,2319,2888,674,4185,4527,634,4728,4171,1337,4349,3352,1553,2806,2804,2612,4856,1371,3044,4300,1659,1306,4036,573,649,2421,2987,3708,2383,2834,1736,4307,1033,4962,133,3367,272,3560,1074,2609,3740,1480,2487,537,490,2824,2750,4565,4263,2365,2643,301,4860,3185,1382,3342,3646,1674,3305,426,4452,627,3285,3213,3241,153,2650,2484,2714,179,2572,2269,670,1618,1761,124,4821,216,4400,4880,675,3852,3534,1847,2035,2925,1101,3148,949,512,2350,3127,1373,2665,4568,2515,4755,3637,4570,298,1662,1923,2528,4279,3753,2333,4696,4498,2768,4605,2686,3068,3362,56,3597,3866,3443,1683,4820,3941,3060,2956,4561,4571,1840,3616,4569,2473,4716,4122,4685,2763,3551,2074,1721,4544,3758,4910,267,3009,3826,3440,4598,1423,2171,2712,4631,3096,563,833,4929,1757,3750,1524,3303,2499,4106,3819,3438,4732,191,4249,1303,2326,3063,3388,3293,870,4580,1827,1703,1682,654,3977,3927,1162,4406,2464,609,2445,2212,2967,4351,3386,2756,278,4261,4446,1453,594,2156,1868,4999,468,1459,4208,1563,1153,792,3566,4673,3038,4011,747,3981,4244,3291,4303,2826,396,1040,2792,3840,1439,4181,2387,3070,171,3426,4195,2040,130,3043,2922,1233,3410,1865,3574,4947,2306,4611,997,1702,4363,3691,4546,545,3692,1329,4411,2370,3712,3120,2633,3718,1367,1372,1279,2321,740,745,2152,4311,4921,4555,1605,2823,4051,2906,3435,4299,2195,3548,1131,4588,692,1797,1744,504,3979,3975,900,2526,684,3837,4463,1436,1291,2046,2708,4730,1943,737,3629,3526,2161,3639,679,2909,2201,1195,3654,407,399,2486,2599,3908,1655,3873,4315,2482,943,3760,2558,1570,814,3863,739,4129,460,687,2451,4649,2386,3579,4456,1579,2122,3464,1775,800,1561,1890,4874,1424,4681,1361,472,1544,2867,4579,3711,1218,2368,3531,4868,2930,2815,3807,4385,4700,4280,707,4316,3317,174,3498,2897,999,2902,3040,601,3309,369,1628,4033,4207,2398,411,3810,2868,841,502,4188,2767,1288,2863,774,2477,225,3344,1656,166,432,2414,3263,3140,4981,4662,3463,3665,2793,756,4105,3248,3496,4217,1047,3461,3674,2892,2519,884,782,1528,3346,3055,4063,481,1728,1481,2544,3834,2078,2724,843,3356,2992,3284,2713,2069,2842,2408,2931,3991,4284,290,647,1804,971,4484,4041,1010,995,1568,659,437,2263,3737,1894,987,3083,3770,1808,2788,2300,4289,18,2305,2965,4841,2424,4113,2725,241,4805,4850,4169,698,4082,2346,2531,3675,796,646,3734,2610,1402,3806,2172,4733,38,1378,2303,297,4313,641,2042,4253,1259,3333,2900,1501,2077,4689,3156,3943,1916,3402,1046,2050,4132,1956,331,89,2323,2049,4857,2126,4934,1527,895,799,1878,1126,1068,3699,2031,2463,3363,2646,3789,3170,5,847,96,3336,257,2489,1148,983,1446,173,1891,1710,1908,881,2108,1700,4147,1239,2549,2315,3494,3071,4331,2449,1835,240,3179,132,3445,4547,2448,249,3594,4607,404,4408,4985,2429,3119,1132,4272,4749,2149,3971,67,1198,1444,2354,2517,4395,4414,2979,4779,2272,4707,1636,4771,1256,1183,3257,4834,1069,936,2770,914,3115,4204,1582,1418,635,1339,2500,340,4133,4329,605,295,2194,4387,1549,2006,55,3667,2382,2202,2330,759,3415,2491,701,1174,2704,3978,190,1249,2104,2409,2697,138,3614,2468,657,4894,1550,3444,1672,2249,1290,3134,3856,4309,90,2218,4344,3488,221,4731,1235,4639,3948,1234,4739,3630,2711,3649,3076,538,4972,2304,64,4124,935,3142,2783,4405,802,1787,1985,3886,4839,3057,3828,2703,4308,4271,902,787,3669,3617,986,2219,4919,3743,709,3051,2795,1759,1497,3967,2693,3850,4790,1765,454,1766,1343,4334,2585,2286,4900,919,1677,1585,2417,3214,2355,52,4516,3502,4332,2736,4635,4454,482,964,4478,2980,4231,2081,1044,3839,2308,3348,3571,2698,3182,3417,3799,1571,3710,822,2136,853,1910,1012,2196,4215,2112,3509,3554,4490,3904,2258,1687,2406,2056,1790,530,4831,510,4949,3732,4892,2454,1038,3640,673,1088,1330,4942,4854,1260,1556,3763,2715,1193,920,4007,3251,3538,391,4690,4001,4680,1104,1947,3233,703,2101,1792,2466,2260,4745,161,3598,1114,4302,4070,1740,4372,4163,869,24,3098,3831,4939,1834,3651,909,2045,4678,4190,1327,2677,952,3454,1066,4005,3501,4871,3075,1294,2226,1158,842,1802,3724,1096,1709,1863,378,4767,3861,1828,4388,951,4291,4060,1824,2038,3345,2385,1205,1925,2007,1240,1314,1136,1712,547,2778,3522,1912,2003,1206,963,3191,4870,395,1043,4969,4703,3052,3688,4718,2005,1464,4425,4382,1814,3877,639,3707,2570,3144,3160,3085,495,1818,2530,726,581,347,1534,1447,4123,4536,816,2564,2364,3314,4676,630,4342,3577,1755,1507,607,2446,4617,2216,4445,2094,2106,1482,108,4143,1400,4191,3290,1606,4599,3049,1463,1690,128,4161,2331,1105,4514,3933,4319,2131,2133,667,4378,3407,22,1090,2128,2137,4218,4012,1141,4886,2949,4628,1997,312,3332,1189,1784,2839,365,2848,3915,2335,1948,3844,1036,2577,4358,3875,1819,3687,419,717,1652,3476,2432,4061,439,3015,3595,3032,1307,4795,4102,4496,975,97,1161,197,4608,3666,4952,3849,1212,1993,2436,4466,3935,4255,4216,1864,939,4905,4137,2969,2935,3268,4729,2041,2080,749,4556,4878,3689,4720,4264,3441,1914,1389,1207,4177,438,2742,2674,1296,2264,4444,470,3593,3792,2008,3378,1429,2695,2441,2759,2420,2179,3995,51,2581,2850,3602,1791,2701,1493,4630,3587,2985,2183,1604,4286,4115,2541,1469,2645,2872,4486,3274,4373,4421,4578,1243,3046,451,3174,1722,2556,2167,3862,3128,4333,478,577,3697,3945,3505,2360,1448,336,3376,1793,3968,1181,3226,4583,901,1384,286,4290,2523,2470,379,4381,825,3787,61,3903,4893,1574,2929,864,4655,180,2428,1646,4646,2745,3613,2557,54,4054,2180,4004,449,1128,656,7,3197,731,2234,4541,4647,176,2416,3041,2510,4560,4896,4528,4818,1075,4297,2067,1106,3796,2372,3260,626,2257,4998,2020,3682,1684,4833,4032,3702,2048,1756,2590,2757,719,2182,310,4499,4961,4494,1335,168,2093,3298,2220,1186,1877,923,831,2366,2299,4150,4699,4521,2862,2602]
B = [2822,275,2670,505,1775,2797,1249,3285,859,1542,1337,1009,4421,609,2050,1819,4533,1437,4364,1148,3396,4778,3306,867,4523,3941,607,3978,2187,1657,248,4935,4886,3889,3713,4752,419,3343,3159,4921,1336,944,3916,487,4630,3877,691,4217,384,3636,3362,2439,2156,4370,3779,379,201,1173,3601,3488,1607,1792,4897,1802,1457,1846,2727,2342,627,2939,1500,844,1643,774,580,917,3023,4296,2635,3501,3103,448,1379,2733,400,2755,3617,1294,1767,4700,4679,1439,499,538,1744,723,4908,2074,2013,432,177,1171,1301,3327,3965,824,4850,4762,4305,3120,1541,1509,2501,4035,574,3221,2719,4873,4573,4901,2926,1600,3527,2264,3583,283,1671,3785,392,556,1854,3676,4295,4928,1471,2047,3008,3663,3409,501,4937,4176,2179,2735,2085,428,2305,3049,1559,3665,2801,333,4349,4,4192,1543,68,2969,3972,3750,3623,1025,1966,2061,1906,1667,3936,2890,3802,4414,4348,523,2546,2549,4795,3505,2957,2444,2857,2946,29,1847,2206,220,545,495,470,4555,407,4581,2114,2844,2303,171,2034,2888,1735,3547,2783,640,4478,36,514,2202,376,37,1481,1784,2322,1203,2092,4840,2434,1030,1125,2579,1425,4544,2247,552,976,3967,3014,2906,2561,1951,3514,293,4250,1710,680,3476,3009,4408,4657,899,4915,3803,312,1309,2298,1003,4514,2838,809,4363,1176,2205,3433,4040,4891,2316,3690,4050,4280,162,2177,4645,4968,4730,434,3449,888,344,4882,2142,1973,4338,1805,1113,3957,1515,1631,664,575,2145,75,1156,550,2925,4425,4496,3642,677,4286,780,1407,1597,2196,1876,3900,243,225,2988,3201,1816,1584,2440,3512,4076,84,129,252,3725,789,692,1988,2172,4196,1306,3116,860,3982,893,4158,3520,2383,4157,2350,3256,1612,2557,367,4912,802,1820,4858,2044,4205,2655,2664,4378,1303,3257,4164,130,2448,4284,3895,1494,1909,2209,2803,4112,307,2937,1122,1194,926,2784,4302,4894,1089,1406,1456,2433,4352,813,264,1473,1686,591,2960,2014,1580,1001,3483,571,1599,1754,349,4498,1354,2494,2031,3499,196,230,4509,2217,460,4672,3301,950,1280,325,940,792,2510,4214,3858,600,268,153,3062,1451,3638,1562,1483,4564,3657,1077,1571,660,2042,3308,491,1189,3530,2125,2174,673,3559,3328,4178,1567,2412,324,2631,3979,645,551,398,2121,2263,2955,2592,1333,2796,1659,4646,1311,1681,1468,568,2338,1852,3495,604,4340,4188,4463,1887,1998,4292,3316,3622,1403,4324,2478,3218,503,3310,4687,1041,4766,138,1701,370,387,2437,2737,4115,2539,4232,4655,3234,1638,2419,2302,1736,2854,4084,4984,1888,3822,1894,4702,1154,209,3591,3678,925,763,186,3681,2057,3621,1411,3646,2425,170,2989,4599,3800,3807,3422,2076,2779,3209,3022,4588,2411,1498,2756,2540,738,3730,3460,3509,2138,2704,3840,555,2535,4587,416,4027,2318,2024,4997,883,4670,2873,1127,4924,3101,1455,4267,3672,1353,3031,1853,657,632,4683,2392,3992,3352,4488,3693,2821,2524,26,286,3376,2697,1420,3757,3178,3648,1051,3091,3714,2734,4225,3283,4121,435,1836,4624,2011,1462,3774,4701,102,3148,1169,2468,4697,352,1237,389,1232,359,1453,1435,755,4503,1945,1472,1050,3668,4943,747,475,4168,4885,979,1948,1795,2528,1636,119,1763,1423,4906,4388,3333,2619,1098,4623,458,4474,4012,1655,1506,3819,1831,2495,1691,3268,1722,3216,4889,1083,902,4934,3465,714,2870,1346,4848,1475,2589,597,2331,636,2236,2792,1195,544,2746,1186,2776,2566,3395,3549,3594,1665,4716,1341,4627,2597,515,1470,1840,4516,934,1035,4221,2231,4992,2506,894,1316,3491,3842,4871,65,2241,779,4843,2650,4980,2608,973,2963,812,2582,3536,4445,2795,2487,318,3694,3051,1276,1715,2207,4247,1626,589,2587,757,1259,4109,4854,3164,3282,2082,1036,1979,3999,1552,2973,1826,3032,1493,4520,4983,323,494,3229,841,1757,1953,31,1484,4953,4933,1976,239,4276,2056,2265,1592,1923,3688,3692,189,831,1465,4443,4209,4808,206,4665,1688,2614,1497,2464,4737,15,4434,1904,4844,1146,67,2249,1732,3037,2932,3903,735,3602,4974,4026,2830,1020,3596,2834,346,4989,4508,3479,4566,3674,1097,807,1555,4465,618,2502,2718,3129,1367,2184,2666,2810,2940,3727,4078,696,3630,4318,85,2593,2395,3882,3089,4902,1140,3590,4789,795,2451,2192,1704,3230,928,1603,2378,2903,4673,1644,4438,1942,741,655,2170,540,776,473,3519,1032,1661,2660,2965,4483,4141,2977,4832,2725,2069,1116,2455,2612,449,2141,214,4827,1339,3756,3445,1299,731,4393,1565,518,2663,3994,2143,4981,3387,3883,3567,1302,2216,3761,1773,1663,4480,4471,4595,192,3372,2393,4136,1544,2234,2762,3228,3036,4106,410,1772,415,255,2274,652,1677,1634,3811,1377,2927,4831,169,2818,3927,819,3524,705,1577,2488,2429,4400,3482,3940,596,4282,1279,532,3566,3810,750,2079,4334,1192,1647,2517,720,2819,4556,1499,4233,1583,3908,2674,957,1936,3593,4801,3945,4090,2067,403,48,1554,3322,350,966,2090,2923,2605,3949,197,972,3251,615,690,674,2111,2878,1576,2851,1350,4376,3508,2226,1441,527,4880,3738,921,843,1742,343,3324,511,2679,933,1956,106,1640,1622,4814,2279,1452,50,4308,3305,1268,2382,4892,999,77,356,536,3857,878,4384,1913,2990,561,1794,4031,4982,2731,4095,1386,1839,482,4143,3595,1464,3043,788,721,1149,4087,3918,3706,4262,3789,2193,4052,1323,1633,4491,1625,4787,3413,178,1017,3791,3778,3477,1170,227,3217,3987,1272,3174,1679,3726,2095,1043,4970,3172,1829,3377,4914,174,4550,3703,32,4798,2584,1832,3273,2966,4361,617,1307,2346,2364,1731,7,3970,1971,981,1814,3088,351,1902,4448,1527,611,3313,3517,1889,194,1646,4528,1869,4219,2401,3425,3732,4266,606,1175,659,3731,4929,2161,1724,4423,2934,3564,4965,3018,3865,289,453,2059,2695,4199,1182,3138,4515,2257,3382,1229,702,4590,3836,3312,1548,2748,3274,4639,282,2309,3554,3816,3542,124,3034,2930,4575,296,3291,1863,2656,3604,1405,4562,1961,1217,4719,2260,2351,2038,4152,2268,665,2283,2340,3647,2720,2326,462,4107,134,4539,2023,4341,3504,4713,498,2533,3961,4033,726,4986,2653,737,2530,1684,667,3586,2064,3415,2199,4461,4878,2852,2289,2200,1163,2052,2482,4966,2026,621,3801,592,3868,1445,1213,946,1803,4079,1174,4089,512,2519,565,3237,4416,3354,2387,4441,1750,983,4671,3766,113,2380,4470,1503,2306,3718,4991,2556,987,1982,4238,3161,3680,4260,3641,4561,1393,4598,2189,3233,533,2154,4023,1924,4538,4179,4418,4634,2823,1997,3976,465,348,76,2301,3244,3402,4728,653,340,1211,207,4846,3872,870,468,2424,1591,3741,2550,2743,2130,909,1572,2276,3859,3954,2654,4537,4387,86,1401,2522,3119,1458,1535,4159,3864,4083,4294,3135,2753,1049,366,51,2843,4201,3782,132,411,3610,2867,3028,414,3507,2029,4326,4926,4226,2240,3685,793,1996,530,1980,2447,1004,4822,118,3540,103,1133,547,306,2649,4999,2277,1867,2131,3708,1899,4377,1431,1419,2083,4444,2273,1990,2003,4390,211,903,583,3121,3656,2360,1769,1649,4099,1759,840,2959,3160,3808,4228,1335,1827,1568,4772,24,1172,1727,1415,2483,3959,4833,4420,876,3723,3337,273,2877,2442,223,4198,1705,2565,182,3197,3796,3654,1129,901,1801,4740,3489,3071,1177,3515,2469,3953,3689,4862,1334,1486,4565,3254,2413,4739,4521,1842,121,3991,3890,2886,313,688,3083,2976,1230,154,4571,3238,4207,2237,4606,3183,1305,2515,1438,1460,2787,3029,4293,481,2312,3371,4466,492,1728,1433,4770,626,4161,1109,3124,377,443,3904,87,1718,2836,157,2398,4800,90,4450,2183,3909,4969,4807,4113,4446,865,2436,3892,1734,3777,2168,39,3888,3609,1528,1761,3502,3024,3118,1208,898,2399,4584,3211,4073,1978,234,2188,358,1320,1618,1281,1916,397,612,1376,2632,4661,3173,1768,3329,2601,3319,3928,2389,3401,4663,4477,869,4975,381,334,4788,4268,3066,3856,45,2427,63,444,635,963,1398,4016,3279,3751,3109,889,2899,3863,2629,161,4691,3640,4534,3364,280,2160,920,2106,3394,16,3386,1180,204,958,749,3281,3381,3760,4183,3420,1291,4976,2891,469,2358,2712,1575,3131,3651,2875,4301,2766,4958,3295,1711,3486,2997,1261,3235,1950,3734,4230,608,3828,3369,2089,4072,715,3205,4435,4931,613,1298,2084,643,2422,3153,2032,4110,1181,281,4512,1283,2197,4712,3168,3958,3804,1776,4938,3400,980,2191,4088,1985,1381,2388,2497,2445,4900,2961,2421,1798,1143,147,1787,3946,2449,2545,964,4998,1520,1874,1897,2321,3202,2315,4838,1487,525,463,2689,2477,4359,1533,2403,1844,2136,4150,4229,4163,4967,2232,614,915,1719,2555,4715,4518,4608,3598,3222,474,2080,3964,2354,1069,4189,89,2147,3074,3633,595,4484,3056,1947,513,1227,1723,459,3140,4777,2155,1318,4479,4215,689,4582,770,787,1616,1064,1106,3019,1167,4835,1056,4917,3871,4059,1674,3365,3053,2676,1962,3356,4750,3239,1327,1191,1013,1650,141,3339,185,200,2018,4799,2817,1075,4836,1265,718,3847,2662,4622,1635,2825,3249,4860,1052,3577,3854,2588,1091,4067,2075,877,997,88,2493,2701,1911,2643,2637,519,2708,4591,2036,300,1321,3259,4353,647,2887,4522,1939,1252,4524,4032,166,2,756,4753,2474,3157,3821,1925,4172,2443,1038,3307,3576,3428,4426,3388,4019,4160,754,4069,3894,2572,3812,2948,1808,1817,1014,3873,1225,815,4175,601,2304,2786,3835,669,3939,2365,2832,782,3195,314,1778,2845,4440,4371,253,3457,3911,4024,634,4548,2465,3848,1135,4147,4638,697,1466,1837,4847,4810,1593,2563,4868,1412,57,1885,610,2261,3755,4816,1830,4080,2410,3853,1855,1733,1008,3792,2505,885,1963,2669,2118,952,1198,3518,4890,2295,3192,748,4754,2060,4583,1534,2537,363,4319,3592,2750,3635,2921,2471,1881,856,364,2016,3637,646,457,96,1158,3200,22,3624,1860,3232,993,3357,2307,4834,3117,1892,3450,3185,4002,1804,4746,180,1596,751,249,105,4145,4830,1228,3532,2058,1823,1284,1586,825,4485,849,4949,3338,3139,4034,3391,4486,430,2602,586,4751,678,4803,4792,2898,862,1277,4977,3846,2521,4111,4749,2516,3704,1270,3145,81,3712,2333,3528,3829,4662,1102,670,2874,454,3701,797,3571,3968,1664,1812,3269,4385,4990,510,1234,2255,292,563,3478,4328,4431,911,2337,1748,1200,4502,3226,3875,4724,4462,3537,4048,3492,1944,3997,3320,1865,892,598,4863,3539,4417,4994,1101,4407,3813,5,2769,4153,246,2446,399,2992,2739,2911,4412,4174,2010,2863,2820,4785,4708,4075,4200,773,3215,310,1427,2293,2738,762,1896,1399,311,3110,4316,3212,3166,4614,1653,4307,1877,4210,145,3759,4100,10,1615,668,3535,2017,742,2828,1843,3311,2105,1770,4291,2039,2204,683,785,3632,2975,1864,1235,582,3824,4056,968,3389,2406,1918,4535,233,3150,1566,3915,4812,834,284,4859,3771,4705,1558,1716,4579,3047,4821,4367,3990,44,4574,3286,4432,1053,4482,650,4696,3643,3715,3616,1995,4007,4343,2571,4283,3347,4259,2677,4085,4120,354,2320,3523,4442,2915,1779,3600,3318,4365,602,1117,965,3250,4823,1199,2644,1800,2902,1394,2461,193,4042,4881,2657,4941,1011,2858,4557,2723,3181,2091,2791,2943,4735,3996,1871,1220,2848,4748,1250,918,4306,3921,4920,3841,1343,4594,2856,1783,3473,3924,1672,3266,3474,1190,1507,2475,2859,70,3472,1295,679,3246,4333,3263,1765,3100,2275,2492,3290,3710,3203,3025,445,4300,152,3881,3679,2033,4197,3055,3655,3390,2680,507,1824,231,2698,558,1221,2917,3004,2853,2628,2804,3925,1605,4156,2119,4779,3085,3265,4066,4312,1910,3335,904,91,4896,1330,3597,3763,4366,1999,4351,619,256,1362,2053,1841,316,3299,4755,3794,4815,2620,4580,1531,2827,4963,2529,3606,4527,4942,4631,2741,2450,2253,2808,2993,2754,4813,4185,1669,939,3410,4074,2829,2418,3711,4036,4335,4251,4784,1086,2134,4845,1972,1266,4612,2349,4424,1791,1467,4194,274,382,4619,3629,3314,3510,1560,2308,1698,4893,3691,2005,4313,2467,882,2885,681,212,2367,2363,988,521,3441,442,2150,4593,4309,1039,1165,1459,2153,803,218,3605,2368,3634,4021,560,345,1685,1233,3005,1751,4166,1933,693,2987,2101,2839,80,155,2129,3060,1319,2040,19,4600,1813,4922,2278,992,3481,4093,3989,658,1242,548,1510,1774,1793,1044,3673,1373,4962,3419,4245,4861,3818,2180,4879,1226,2503,3935,838,2658,1388,478,3188,3098,4819,2384,4633,684,2002,814,3277,4996,4389,1396,1764,772,190,2415,1859,2548,3436,2452,3471,2164,369,2166,1288,1914,1002,2978,4568,3378,4644,4559,593,4690,3960,49,1236,1930,1223,3861,3569,144,1476,2167,4354,3793,2072,111,3458,1446,4182,339,456,431,3493,271,1981,263,3367,1850,995,3144,3180,3919,4501,4688,4805,301,1144,2511,1811,2220,734,850,1785,846,4883,3735,730,396,4086,2254,3768,3147,1332,4946,4887,3870,480,1513,1408,3133,1231,3728,4648,4732,3179,40,1848,4058,4452,1057,1670,4126,100,1553,4640,1340,3076,712,4047,4102,3984,471,1300,1551,2259,160,3108,285,806,433,3599,2000,4790,1121,1065,549,4604,4629,1355,1695,1693,3611,4570,4003,2892,4429,1590,2311,1927,4865,1087,241,2880,2391,1522,4925,623,4193,2651,329,818,4459,2938,2479,4567,2751,423,3432,701,1479,1608,3199,1908,4699,3219,1404,4493,2894,4374,1325,1254,2564,165,884,2285,1737,156,3194,4927,3366,761,42,3671,2901,2639,3574,4678,830,996,1965,4303,3196,3334,874,142,4856,163,633,4723,1359,3797,203,2951,3705,3799,1080,1364,3985,622,1594,2995,4553,4668,2710,855,3963,303,3061,1570,1954,1164,2006,3006,4289,3820,3446,3094,25,1989,3017,800,2325,967,4320,1429,3442,2711,4252,2686,3644,4020,2124,125,131,1205,372,1901,3348,4586,3165,2732,919,2641,1578,1862,2866,4131,3379,4097,188,338,708,2271,2456,3258,1730,332,2176,391,579,3323,2972,4641,2636,557,531,1114,3937,687,195,2377,808,3455,404,4733,242,1375,716,1104,3659,3330,3686,4867,2683,4592,3545,2258,1547,1690,3252,108,1060,1630,4270,3151,110,2028,3146,3072,836,833,2954,1238,1448,526,299,4138,2171,3827,567,686,291,2063,3236,422,295,1919,3152,1214,1915,4402,4905,1006,4386,221,151,3044,1883,534,1360,2935,2547,380,2267,2284,4123,1210,2430,3452,13,3926,4899,4044,4903,1328,4053,47,259,700,1079,1526,629,4165,1984,98,3170,1078,385,2498,3095,2221,294,3901,1610,2107,1517,4231,2780,240,1968,1658,3142,2454,3699,3214,2538,947,2499,3001,1766,1621,961,4540,624,1986,4526,4597,2968,1084,1289,2618,1797,805,4133,4473,3086,2869,3190,2707,4864,2292,2665,3466,3884,3416,3944,3675,2736,2195,302,4323,3177,3684,1477,3506,8,875,2652,64,2400,2703,1488,3208,2297,3134,4703,1342,2144,2774,4249,1397,2626,4331,3612,4382,3497,732,4455,3302,1258,1760,4532,4008,2296,2568,1712,1197,2051,3404,1780,3385,309,373,2122,1246,6,386,2219,2128,139,2348,4383,1934,3287,2603,2642,2112,2329,1436,1262,4913,393,2964,1130,3653,3534,3658,4572,4578,1938,464,1856,2356,4135,594,4757,4049,1024,2981,4237,953,1573,3013,1059,2624,4610,866,4360,651,2721,1094,1118,4802,3697,4950,1124,2327,1604,4698,4876,4955,1708,3361,78,3418,1312,4043,1082,3184,3899,1271,4134,1524,123,135,3167,566,517,3929,2227,587,2527,1338,244,2015,4381,2390,1275,804,4094,2835,4842,1062,3831,1054,1828,4146,2127,276,4180,2559,3753,1209,4025,4410,2813,83,4256,4995,3533,736,1977,3104,3189,1058,1382,3225,2310,4607,2163,4130,4241,506,3980,2526,395,1993,2999,2230,4756,962,2246,417,262,20,2928,2108,1537,3500,3830,3737,3494,3045,3468,564,1012,2745,3720,1326,3490,3661,4499,3851,2117,401,2562,1512,4148,2600,1958,2250,3952,2272,4063,2347,3746,53,1111,4653,3213,1443,4415,2675,4985,524,406,4960,1687,1749,3143,2764,4244,2362,2280,847,2807,829,3405,3587,198,1519,2782,357,3683,2985,1018,2496,2884,4206,4411,1699,4874,4909,4839,4552,3834,4433,3136,3440,4395,3740,1937,4327,864,2148,3767,1720,1886,2861,1880,845,872,3886,666,3058,4001,2767,2381,4350,863,1838,2397,3855,4139,811,2554,199,18,1641,2339,175,2777,52,2947,3403,4596,1119,4797,4569,361,2490,3007,1935,2486,388,4500,1619,4436,752,2991,2913,4947,3163,927,4549,3553,3531,4605,3932,1851,4243,3241,2613,4761,1673,1463,104,3042,719,2700,955,3296,1243,1563,1587,476,1096,288,4346,1550,3050,2788,4223,1215,2314,4769,229,908,3346,1141,257,4895,1308,1136,11,143,3046,4884,924,2366,4430,4329,4362,3421,1179,2855,4853,452,390,4492,3284,2907,4765,4030,173,584,3719,4731,3123,2742,265,1449,1168,3707,1928,4467,2800,353,4028,4782,3,4857,1516,820,2758,4666,4793,3137,3345,92,3253,2214,3383,2428,3102,30,3444,4692,4519,3020,2520,2198,3487,3115,848,2373,3080,4391,3627,1085,4277,3614,269,1253,2919,2186,1357,2544,698,1825,937,3773,368,2077,3264,573,703,2323,2470,226,3309,3081,504,2625,4923,2699,1922,1414,1579,1682,164,3869,2681,3374,2020,496,3105,222,3075,3628,3969,4046,4545,2009,554,4693,2182,1504,3998,4818,4773,2576,3748,2218,2385,4254,3443,4743,746,4718,1898,305,1940,3557,3467,4272,4129,2647,1955,425,4311,2244,2790,1356,2215,2420,2151,2876,1809,2604,2580,3649,2087,945,2586,3809,4104,2882,328,1088,2116,4763,342,3581,3155,1366,4321,2611,1081,3242,4253,4988,4504,2922,2633,1777,2872,1496,3733,3114,247,4475,2983,1678,4495,4103,341,873,2512,3843,4714,1263,2158,4155,2146,3790,2724,4563,1240,4332,4224,4236,1147,931,1706,4741,3485,3589,4615,3434,3227,4015,2617,2152,1585,2203,4494,1241,1929,4744,1076,1675,4116,1536,4961,2542,4684,424,1545,4014,4298,2229,3747,4706,4439,2744,4637,3350,822,412,4554,2980,2687,3913,3223,183,3341,4722,3077,236,1907,569,1410,1218,4202,3064,1651,1994,1492,4314,1371,1478,3511,3469,1021,2022,960,3298,279,2847,71,4101,3041,488,930,4476,1324,2266,2287,3849,2599,1138,3353,3550,1557,2408,3585,1539,54,1490,4781,1257,420,2634,4664,1108,3973,1756,79,4681,28,4142,1474,2920,2661,1926,671,642,402,347,2691,321,1983,4281,297,3744,4265,72,871,3698,251,2025,2668,1845,1073,187,4339,2688,2299,4275,3729,1023,3575,975,4396,2781,2027,232,1683,2441,1040,3245,4979,1278,437,2282,4045,4118,1178,1074,4649,3786,4677,3012,978,3090,2806,1392,4547,1204,1771,1598,486,2799,467,4065,122,1310,3411,2577,4208,2998,4776,727,2578,3880,4051,23,1758,1461,887,61,1799,1680,4558,3613,2659,2794,1903,2850,3002,3588,1895,3393,2868,2100,461,2607,2473,1782,1161,4656,1807,2374,1416,4636,1297,4038,4791,93,4380,2860,713,4851,3914,2728,3770,4530,335,2994,1131,2481,2805,4317,2081,1662,1450,3059,3947,1383,3175,1159,1244,3584,3764,3934,3762,3454,905,1890,2865,3456,1251,2438,4114,2702,542,2573,1282,3262,1931,1762,1126,4725,1363,176,4771,3615,1434,2684,2243,3067,4497,1868,590,3288,1564,4576,4621,990,1193,2353,3141,2065,4394,4140,672,1588,620,1155,2871,4144,3206,1046,4458,1368,250,219,2831,375,4481,3429,4589,984,1709,319,3529,4837,826,1959,4105,740,116,1530,2409,662,228,2616,1273,588,224,2840,2181,4132,2692,1063,426,408,3667,699,1160,768,1256,1648,929,1005,2507,3453,3122,1882,1569,4852,450,3158,4729,4758,942,3384,298,2459,2879,1967,2798,2525,1361,3498,2944,1037,1447,641,1103,3052,2904,951,4203,3776,4091,2924,2814,4419,2159,1142,308,3906,1857,3503,2286,3563,4264,4186,4447,3898,3619,2088,4654,3784,3289,2208,1629,1047,2055,1033,1055,861,581,2094,3373,3408,3255,1454,777,2594,1293,1529,3525,1620,572,3326,4068,4310,816,1019,278,1613,2414,4513,2099,1390,2812,4427,3742,3359,1875,4009,2646,1753,2815,4658,1482,1351,1491,1866,4796,3448,4806,1932,2416,2233,1313,2621,1352,3639,2958,2785,2793,4817,2760,4122,3035,2974,1387,4531,2936,3325,1432,2324,205,1440,4957,4536,3580,4096,4082,4585,1790,1873,1628,744,2379,4211,2895,365,2270,1905,4651,4617,1525,3082,4972,1187,4811,4775,261,1623,2372,1788,409,2480,58,1317,4017,2918,4191,599,479,1428,4936,1858,570,3650,4464,1260,3087,2054,2489,4720,4543,3573,4469,1480,2132,4457,3582,2693,4686,3368,4451,4973,695,2583,2096,3780,3722,1331,1292,4235,3187,270,4330,2194,4274,2097,798,2030,922,1042,1946,3837,4125,2773,3462,3113,1000,2765,3912,3839,4487,477,3879,4287,2113,535,3423,3572,916,117,1549,2667,136,3931,4269,3033,3893,1007,1157,4449,441,484,900,4242,4841,1132,2883,2585,2569,4077,1139,3862,799,3414,644,2716,3787,3867,1264,3838,3516,4204,172,3783,3220,4667,3852,1090,33,2761,3240,4506,1920,4742,2536,936,559,4944,4041,101,1835,998,2730,2837,2553,2223,729,2300,605,4734,1422,1365,1833,2726,4710,880,1861,1095,315,835,3971,4601,2864,879,3798,2068,2343,21,4951,4704,2281,446,2248,1185,56,4060,2341,4240,2140,3000,2407,4227,3579,2816,4369,3292,3920,759,1818,3974,2394,2846,2722,3907,1395,3480,1029,4916,616,1741,4011,2881,2909,1781,3833,2139,440,3562,1745,760,3360,2509,910,1286,4304,4169,12,330,2041,896,3303,2833,1031,676,3198,2534,989,2717,3272,2046,3069,529,1322,3003,466,625,213,2541,4647,2238,1184,4490,4409,3826,1957,3336,66,4759,3717,1614,2162,974,1384,322,3424,2713,82,337,1068,3112,3825,3765,127,912,2581,1952,4529,38,783,1026,2893,2491,2648,3162,539,3297,3210,3247,4875,2361,3664,537,4092,158,2402,4278,1418,832,4685,2809,3662,69,956,1738,4246,394,3106,3513,1521,3438,4948,725,1022,1247,3016,1627,994,4551,405,3461,2908,4337,3845,4849,4625,1707,4825,710,4745,3321,2330,2986,3769,4794,3430,628,1696,4511,711,4154,1810,638,4978,2211,378,2212,2747,2462,3380,4659,1870,2900,4257,4018,1166,4460,3398,4952,490,2201,3464,1632,94,2609,1349,3331,1713,1267,2770,383,2396,4642,949,62,4297,508,2225,1815,3193,895,3073,982,766,3132,2045,4356,971,3962,1329,427,1400,1120,1900,1202,4546,2567,2043,2706,43,4128,1380,2518,120,2949,1145,3560,2021,2335,2933,3897,1150,4676,2615,413,3097,1469,140,3437,3344,2623,516,287,4181,2558,2178,3231,3111,2789,2752,1196,3561,2262,1666,3558,923,745,3026,2458,707,4907,4786,4171,3814,1015,3526,1222,3349,1100,3975,3431,3107,3521,500,4869,277,891,2359,4804,1611,2740,4959,2104,764,4081,3823,1092,4767,290,630,3977,4399,4064,717,4010,2294,355,3781,3878,4660,2466,436,3276,3079,656,3260,3182,2673,585,4828,2352,771,1821,215,2137,210,4783,2638,99,1421,2570,3541,733,1595,1248,1255,1582,1296,810,4290,1370,4489,2086,3470,4613,3866,1495,2004,4727,943,4643,3603,2457,4428,2996,1639,2531,2386,2290,1921,1514,784,1061,4397,906,95,661,2242,4263,3021,4119,1878,2500,654,2574,2345,823,3874,2165,4809,3439,2222,553,3068,4993,1700,3375,1717,1949,137,2071,331,4609,3417,2672,2476,3551,35,1872,497,3015,4505,2376,3815,3696,260,2019,1269,0,2671,1153,907,2251,17,4261,543,74,1290,2962,128,4373,3300,2317,2842,2423,1960,4239,1581,4910,2426,4392,4299,2078,4273,3207,2715,4315,4167,1589,786,2802,4108,4212,4405,1546,2768,1714,2849,3608,3267,360,4560,1045,3038,3484,3618,1992,2504,1134,1891,1426,2630,2606,2714,722,1642,2239,2126,4877,2375,4517,2435,1,546,1344,941,2102,3687,954,1676,4195,3496,4872,3917,148,3243,3754,758,4004,4542,2404,3788,2228,1806,2157,1702,4279,2826,235,4368,3860,1358,3293,493,1207,3943,184,2682,2543,3010,3078,4173,2245,986,2575,3795,3317,4768,4220,418,2012,1532,4611,109,1430,3204,1879,4602,1245,336,4510,1128,3130,2929,3538,4151,2269,159,217,3459,649,1212,4184,796,3677,1746,4401,4911,3950,3966,4127,2135,208,839,258,4190,1347,4071,2889,112,2291,3758,326,2357,3275,1822,4738,1112,2332,1099,4689,4347,2256,3084,4472,4918,663,1991,1556,3885,3128,1917,4780,2931,3027,854,694,2460,4006,4736,3399,3666,266,4826,1941,1974,455,520,2115,1162,245,371,1796,2952,1523,1729,791,3805,522,1369,1417,1849,4177,3261,4345,4820,150,4005,4919,648,2916,2035,4717,1975,3682,637,2110,4124,3876,3154,1285,528,4577,2970,1315,2190,3271,753,3340,167,3905,3355,3930,1385,781,3406,1115,3948,3412,794,3270,1893,4541,447,3772,4187,817,935,317,3342,1093,4747,2149,3891,2897,1304,2369,202,4285,3552,1345,3065,2485,4764,1137,3426,3280,3607,2210,1789,1239,2103,1689,3475,685,765,168,1694,2749,1943,1739,4288,3427,3625,4650,1110,2523,126,852,483,2685,1755,2319,4940,1067,1505,2914,2532,1540,439,767,3451,3070,4070,3724,2551,3709,1444,1645,1413,778,2109,2073,238,4398,4255,4956,1442,4675,3556,3844,1071,4507,1743,4372,4248,179,4453,1274,3186,1123,2432,429,1609,1834,3739,1501,3850,3435,2598,2066,1372,724,3156,60,4061,2982,3546,272,3544,1151,1314,3447,3922,3955,3278,2759,1606,1721,4406,2513,4711,3463,2910,4468,1485,1206,3736,3752,1224,913,4682,1378,2463,2334,1066,675,3896,4939,775,3749,97,3670,739,149,2093,578,2772,4054,1219,2942,2610,4694,4603,1601,2694,2596,2098,1692,4945,3645,2824,3669,682,4635,4618,3660,3775,4904,1072,4271,828,3570,991,3620,216,2037,2696,4379,3993,14,2905,3938,3988,3543,2984,3743,4344,2133,4358,2862,541,41,4971,3149,3555,2595,1391,2008,55,3986,3887,362,1518,2405,2224,4932,4695,3721,2560,2370,4437,959,3745,2252,3951,3933,1070,1502,2048,1970,9,4707,2001,4218,4930,1697,254,1016,1010,1574,3392,2763,2953,769,3817,4039,2709,2778,4170,3983,133,2591,1489,4037,706,1752,4213,4055,146,3695,3127,827,4674,4322,3995,3191,3126,4355,1726,1884,977,3315,4964,2453,1617,34,2640,842,4062,2336,3363,3407,4137,3397,4216,4616,897,4454,1508,969,562,2472,4342,2945,1747,3063,1602,4726,2371,59,237,2979,4325,3358,485,502,3700,639,4721,1028,4234,4149,3981,1703,489,2811,4652,1668,509,451,2049,1201,3096,2552,3832,4709,4013,2313,1725,2120,2956,2775,3048,1402,3956,374,914,2645,2070,3093,4258,603,3370,181,2967,576,2062,1348,2173,4898,304,2417,631,1188,4774,2288,1654,1034,851,1107,191,3702,728,4456,837,4824,3040,3910,3568,4422,4620,1409,4357,985,3716,4888,327,4870,2590,1987,4029,948,2007,3652,4525,881,3030,1027,709,3176,4628,3351,4222,790,2729,801,4403,1624,1216,3304,3332,1652,4866,1105,890,3171,2896,107,3902,4680,1637,1424,3039,2514,3011,4375,3169,2690,320,4413,704,2484,3923,3565,438,3631,4855,2950,3092,46,3057,3548,421,2841,1511,3224,4632,2355,1656,27,970,1660,267,938,1964,472,2757,3626,3054,2123,3248,114,3522,2328,1389,4162,2235,3942,3806,4057,4000,2627,4336,2912,2169,2971,2678,4669,4626,2508,1048,2431,4954,932,2622,2705,1152,2213,4760,2771,821,1183,1912,853,1740,3578,857,868,1374,3294,886,4117,2185,743,2175,577,3125,4404,1786,1561,4987,858,4022,1287,2941,3099,73,1538,115,2344,4098,1969,4829]
c = 9f8a883d7e045010619a7aba5c0cdeb33ee0482626e2c5e718b3ef955ad9b4986d4406b6a1f53e78e506c7dcf806f964090a1e44fe2737b883