constexpr const size_t INPUT[] = { 2936, 2154, 1578, 4820, 5674, 5582, 2392, 6148, 1276, 1783, 2572, 5067, 3526, 0, 1673, 10546, 0, 1036, 2765, 2244, 1018, 2363, 6858, 4640, 2614, 2660, 4411, 1118, 6887, 0, 3965, 3978, 3991, 8557, 3150, 3801, 5310, 1991, 8961, 0, 8526, 2340, 4983, 3750, 3471, 1564, 4638, 7198, 3127, 5522, 0, 5417, 3737, 7464, 2219, 5174, 2873, 1650, 3044, 6290, 2640, 5499, 0, 1946, 3463, 7792, 6268, 2608, 5922, 3812, 2292, 5730, 5798, 2785, 0, 15448, 14133, 15280, 0, 32925, 9977, 0, 31033, 36925, 0, 7793, 4374, 3042, 3900, 7160, 7472, 6251, 1866, 7489, 0, 6884, 7643, 3926, 3857, 3326, 7619, 2831, 8489, 8212, 0, 8447, 1468, 1100, 6492, 9151, 2144, 6579, 1951, 9223, 0, 28622, 0, 4166, 2686, 7394, 2773, 5777, 5734, 1164, 1916, 4040, 7119, 1986, 5178, 0, 3920, 11406, 1982, 1596, 2852, 9750, 5758, 0, 4860, 10579, 5897, 9117, 2767, 10259, 8488, 1120, 0, 11037, 16409, 0, 3114, 5793, 9778, 5873, 4201, 11491, 3555, 0, 1793, 9922, 21194, 0, 3578, 4113, 4094, 7777, 4623, 4349, 5554, 8046, 6099, 2934, 0, 18520, 22405, 22499, 0, 3978, 20163, 16656, 0, 4073, 4198, 2156, 5691, 4071, 7596, 5628, 7557, 6776, 3796, 0, 10611, 1321, 2692, 8966, 1069, 3168, 11061, 0, 2025, 6601, 2981, 3962, 5499, 3940, 1548, 2094, 5794, 6120, 6393, 5493, 3611, 0, 2539, 2894, 7029, 7277, 1467, 3123, 6152, 1023, 6351, 6054, 5440, 0, 2877, 5142, 4862, 4155, 3692, 7854, 6712, 1462, 7198, 1111, 1548, 0, 3246, 19782, 0, 13975, 11522, 12604, 1220, 4652, 0, 1860, 2373, 3595, 6084, 5099, 3484, 5828, 2102, 5249, 3382, 3129, 3963, 2298, 0, 7770, 4139, 1491, 3495, 5239, 9025, 1745, 2254, 9599, 0, 20903, 0, 1009, 3131, 3866, 9099, 9002, 2730, 7083, 4350, 1239, 0, 61041, 0, 59008, 0, 6746, 5100, 2503, 1809, 5988, 6011, 1652, 1291, 4348, 6322, 1982, 4321, 0, 4090, 7038, 6586, 4222, 8733, 5201, 5132, 5260, 2548, 0, 5959, 6803, 1420, 4281, 1380, 1566, 6317, 3029, 4666, 4459, 4039, 4104, 0, 14286, 13187, 11293, 6804, 9011, 0, 4002, 13481, 6528, 14618, 0, 5247, 9496, 2951, 8130, 4237, 7737, 0, 9223, 12089, 12087, 7816, 9441, 10626, 0, 5465, 3972, 8692, 13696, 11295, 0, 9724, 17909, 23253, 0, 3418, 3116, 5056, 1656, 5994, 3336, 4612, 3063, 6783, 2118, 4666, 1343, 5492, 0, 3910, 4692, 1113, 1799, 5139, 3531, 4893, 2612, 5573, 3298, 1612, 4609, 3372, 0, 1787, 1838, 2569, 2437, 3770, 2197, 3144, 5940, 6248, 4953, 4674, 3697, 4926, 2660, 0, 6814, 2923, 1517, 2468, 6726, 2925, 4728, 4433, 6343, 4225, 4081, 4445, 3555, 0, 6727, 5809, 10250, 7025, 9307, 1102, 7950, 0, 5769, 5786, 3105, 1538, 1836, 2025, 5583, 1900, 2558, 2418, 3541, 2765, 2474, 4071, 0, 3368, 6393, 4684, 4010, 7804, 8291, 8889, 2384, 6981, 0, 2112, 4039, 6338, 2628, 5228, 3427, 1788, 5138, 1891, 4216, 5905, 5629, 4588, 0, 42033, 0, 57235, 0, 3821, 5741, 4265, 2601, 5218, 3592, 1816, 1199, 3577, 4657, 1068, 5495, 1614, 3586, 1894, 0, 3638, 3088, 6292, 2293, 5310, 5129, 4082, 3982, 2596, 2252, 4279, 5800, 4607, 0, 5351, 13793, 10195, 5951, 9105, 9951, 0, 4126, 3798, 1905, 5413, 1956, 2246, 3559, 3993, 2447, 2600, 1478, 5856, 5595, 1416, 3749, 0, 5758, 2495, 1185, 5261, 4898, 6858, 3304, 5540, 6718, 6596, 4806, 3161, 2222, 0, 5011, 7613, 8709, 7915, 6889, 12127, 8855, 0, 3479, 5863, 9234, 9019, 13582, 2978, 0, 10216, 13081, 5805, 3791, 0, 6591, 1319, 1901, 6087, 6769, 5230, 3857, 1690, 1471, 6775, 4204, 2166, 1192, 0, 6571, 9490, 3259, 2326, 5084, 8723, 10744, 8363, 0, 5693, 5198, 3911, 2606, 3996, 1377, 1248, 5244, 3169, 6347, 4885, 4255, 6175, 0, 7476, 1656, 24309, 0, 3801, 5855, 2015, 2516, 1313, 3658, 5344, 2769, 3269, 3797, 6851, 7192, 0, 1254, 1999, 3039, 5211, 2624, 6505, 3214, 6949, 7036, 7926, 2469, 0, 17404, 21131, 13342, 0, 3789, 5360, 2709, 4535, 5734, 5686, 3180, 1711, 1719, 3476, 1747, 3526, 3642, 3528, 2035, 0, 5978, 6149, 7455, 2176, 6878, 2191, 1291, 0, 2498, 7020, 7297, 4930, 1920, 6770, 4661, 4429, 1639, 5593, 4552, 6441, 0, 1804, 8012, 2515, 4692, 3062, 2261, 6532, 6486, 3061, 4968, 1284, 0, 3640, 9961, 4058, 3247, 12036, 5775, 0, 5253, 5478, 2337, 5508, 4905, 5950, 5556, 1425, 5441, 2823, 5915, 2901, 0, 5247, 4417, 1117, 3120, 5747, 1237, 4181, 5554, 3357, 1711, 6794, 3088, 4462, 0, 17031, 7995, 7350, 0, 5329, 2498, 2249, 2890, 1653, 2814, 3465, 2429, 5142, 1373, 1076, 3256, 3441, 2567, 3470, 0, 7072, 6394, 14586, 15340, 10147, 0, 1184, 3671, 6755, 4184, 1318, 5838, 1549, 2264, 2809, 0, 19812, 29553, 0, 5892, 1705, 3585, 1626, 6955, 5158, 1920, 3187, 2635, 4317, 1546, 2059, 3259, 0, 1837, 7240, 8226, 7841, 4213, 1359, 8366, 8041, 8457, 5615, 0, 3400, 4732, 9484, 2584, 3179, 7544, 7950, 7146, 2869, 0, 6427, 7052, 12827, 6005, 5345, 0, 11886, 4904, 15026, 8150, 2428, 0, 5226, 1184, 4964, 7415, 6726, 6062, 3801, 4207, 4667, 5422, 6152, 6809, 0, 11010, 3396, 3939, 10492, 10977, 1526, 0, 6235, 1219, 1240, 3401, 2883, 4055, 3590, 7311, 2287, 4448, 1450, 6571, 0, 4195, 7290, 6159, 2487, 1417, 3335, 3714, 2680, 7677, 0, 2389, 4734, 5970, 4799, 3294, 5785, 4205, 3461, 3951, 2188, 1083, 3154, 3160, 5131, 0, 3037, 7706, 2893, 5051, 2504, 5707, 3270, 1667, 7843, 8255, 0, 3971, 2506, 1225, 4862, 4154, 3311, 4597, 4483, 5029, 2931, 3724, 6267, 0, 5105, 2285, 3247, 1997, 7380, 2619, 5931, 5356, 7503, 1492, 6980, 0, 2372, 9012, 3114, 6193, 9829, 7515, 0, 2994, 2886, 7307, 6672, 9188, 6452, 7227, 1663, 2321, 0, 4061, 4316, 3828, 4449, 6179, 8549, 4645, 2389, 0, 5622, 4051, 3292, 5450, 4050, 5380, 3050, 1497, 5642, 2911, 4139, 6228, 4921, 4164, 0, 3019, 2696, 4175, 5228, 5084, 8066, 2002, 6316, 1896, 5800, 5010, 0, 3827, 4823, 1059, 6860, 4913, 2078, 6344, 4928, 4670, 3954, 5839, 6671, 1847, 0, 8618, 10069, 9967, 5072, 3126, 10051, 7873, 0, 2607, 11143, 1825, 6221, 8017, 9435, 0, 16412, 16329, 1854, 8746, 0, 1571, 2842, 5496, 5206, 2448, 3106, 1109, 3122, 4157, 5302, 5701, 5799, 3679, 2192, 0, 4301, 5488, 1830, 2337, 0, 7923, 3239, 9182, 1888, 6162, 1450, 6176, 3233, 2406, 0, 7771, 6540, 5808, 3970, 4350, 1340, 8384, 2276, 8802, 2848, 0, 5847, 3110, 3085, 5670, 5916, 2571, 2262, 2451, 1622, 4318, 4021, 4566, 5403, 4223, 5333, 0, 4537, 6349, 11104, 12051, 1978, 11190, 4207, 0, 5656, 5373, 3390, 3672, 6780, 5693, 2580, 1318, 6731, 6497, 6087, 4812, 1683, 0, 4013, 5016, 3679, 3489, 4541, 3353, 2013, 4128, 1089, 5016, 5174, 5962, 2476, 1202, 4038, 0, 7860, 3774, 3465, 2578, 2927, 5082, 6238, 4640, 4399, 4796, 5472, 0, 13289, 7271, 4915, 12428, 4991, 7437, 0, 1861, 6704, 9064, 9116, 9014, 3179, 3804, 3388, 9220, 0, 1542, 4467, 4690, 5711, 5771, 4787, 4920, 3270, 4137, 3723, 1897, 3557, 4111, 1133, 0, 31409, 26240, 0, 54757, 0, 11450, 16767, 23519, 0, 2962, 7702, 2733, 4930, 1625, 4819, 8294, 1175, 5457, 2818, 0, 6973, 17505, 9097, 0, 5350, 5398, 3740, 3089, 5707, 4075, 1216, 5204, 2666, 3231, 1938, 4479, 5828, 4838, 0, 7265, 2510, 11224, 4131, 13248, 1782, 0, 9488, 4374, 6103, 5519, 8562, 7159, 1375, 5488, 0, 1831, 4925, 4237, 7047, 4861, 1022, 1128, 1435, 4340, 3034, 6247, 1802, 0, 8584, 1369, 9026, 2651, 1936, 3739, 9534, 1333, 9577, 0, 3422, 5403, 2334, 3151, 5389, 6238, 6798, 3153, 2349, 2507, 7712, 0, 24170, 37492, 0, 10089, 4269, 8807, 4197, 6865, 2465, 0, 11707, 2757, 12186, 7550, 6848, 0, 2872, 0, 4350, 7436, 1658, 5948, 1318, 4182, 2357, 6368, 6596, 6849, 5834, 6740, 0, 4541, 3912, 8154, 8962, 6441, 8402, 5632, 4613, 3044, 0, 15710, 21759, 10989, 0, 2297, 5846, 5189, 4010, 1784, 5537, 1710, 4587, 4919, 2042, 3875, 1231, 1189, 5253, 4591, 0, 3073, 2725, 6203, 7249, 4089, 5208, 4083, 2246, 3511, 3208, 4807, 2344, 0, 2697, 1438, 3037, 4962, 3541, 3306, 4257, 2955, 1545, 3920, 6095, 3218, 4343, 5534, 1427, 0, 6900, 3342, 11170, 11907, 7355, 12479, 0, 1038, 8366, 9232, 8076, 8587, 3629, 4064, 9998, 0, 6287, 3967, 4660, 6274, 2192, 7327, 2320, 7645, 2270, 1937, 4081, 0, 24311, 11660, 0, 59340, 0, 6337, 5276, 1837, 3584, 1694, 5173, 3233, 6142, 6009, 5006, 6609, 3681, 4657, 0, 8509, 7711, 1338, 4405, 8726, 2762, 5390, 7733, 6562, 2982, 0, 4088, 12749, 16144, 2756, 2984, 0, 7631, 7535, 6105, 5294, 4164, 3887, 7604, 1942, 4003, 0, 7843, 5369, 6791, 7812, 8959, 1015, 7660, 8312, 9652, 0, 4738, 31158, 0, 15129, 5290, 10208, 14179, 0, 64834, 0, 17092, 20735, 17584, 0, 20179, 0, 6301, 9239, 5750, 8133, 4043, 1360, 7768, 4443, 0, 1874, 5287, 10423, 8366, 8343, 6700, 8319, 4207, 0, 9296, 1089, 5175, 2097, 14198, 0, 8741, 2040, 1298, 6200, 5218, 5703, 4398, 8164, 3133, 5517, 0, 8203, 11470, 9992, 5236, 3425, 13464, 0, 5741, 7636, 8651, 2228, 3812, 0, 7507, 4962, 8297, 7543, 7524, 4316, 7844, 4957, 3512, 8166, 0, 3786, 4240, 6919, 5851, 5750, 4494, 5669, 5055, 2882, 5237, 5003, 6899, 2143, 0, 5252, 7067, 5621, 1603, 7932, 2229, 8221, 2127, 2642, 0, 5887, 8125, 8737, 10040, 11446, 1559, 0, 2217, 4189, 8380, 8045, 8755, 13228, 0, 54109, 0, 1661, 6203, 5058, 4111, 3350, 2427, 2875, 1662, 1043, 2872, 3145, 2096, 0, 10789, 2296, 1519, 8104, 7658, 2462, 11042, 0, 4075, 25095, 12365, 0, 3620, 3451, 2143, 4928, 2209, 2259, 6291, 1922, 4258, 1298, 5973, 6830, 1690, 0, 6720, 6472, 7642, 3595, 1368, 2802, 3531, 5303, 1754, 5980, 0, 33359, 0, 11749, 3605, 11281, 1446, 6081, 2610, 9589, 0, 4086, 1683, 3542, 1782, 5999, 1239, 3191, 1829, 4645, 4154, 5315, 4039, 1170, 5072, 5837, 0, 5498, 2051, 1591, 3317, 2076, 4854, 5165, 6695, 8679, 0, 9267, 35217, 0, 5634, 6374, 5070, 2104, 5724, 5451, 6252, 2991, 6001, 6377, 1555, 0, 3235, 2411, 4950, 6073, 5384, 1309, 2112, 3943, 1158, 1942, 4894, 3041, 5480, 4287, 0, 8198, 16167, 2116, 4242, 3134, 0, 5254, 1059, 6196, 5498, 2120, 4585, 2757, 1442, 7062, 2529, 3641, 1540, 0, 2139, 17318, 19655, 0, 67758, 0, 13837, 3641, 8971, 8275, 7128, 1945, 0, 1852, 3110, 2650, 6258, 6653, 5424, 6283, 3827, 1203, 1847, 5970, 7045, 0, 3339, 4223, 3933, 5845, 4095, 1658, 4167, 2456, 2140, 3991, 1326, 4503, 0, 3459, 6780, 0, 6017, 17143, 2006, 15617, 0, 6357, 5973, 2832, 2404, 5466, 5263, 2442, 6483, 4672, 6030, 4179, 2206, 2294, 6168, 0, 2526, 7729, 5484, 5537, 8009, 3436, 5436, 7202, 7328, 2660, 2234, 0, 1256, 6714, 6588, 2886, 11142, 7214, 1867, 0, 2905, 3043, 5967, 2667, 1735, 6070, 3982, 6459, 1637, 1984, 1692, 2181, 1266, 0, 4355, 4571, 6495, 2767, 3262, 1740, 4560, 4120, 1892, 4609, 1276, 6129, 5883, 6009, 0, 5508, 1052, 1030, 6060, 3657, 3996, 5975, 1088, 2266, 4524, 7182, 0, 3034, 4023, 5263, 3276, 2948, 4466, 3517, 5358, 2969, 3410, 6135, 5900, 3376, 1312, 0, 8020, 7495, 2147, 1390, 4096, 2477, 7974, 4165, 1039, 1034, 7495, 0, 2474, 1473, 2810, 5689, 2742, 1972, 3315, 2083, 5077, 5477, 4451, 5582, 3126, 3173, 3823, 0, 11214, 7922, 4212, 5624, 8534, 7311, 11637, 0, 15693, 3473, 14621, 1422, 5178, 0, 7968, 3381, 3653, 4254, 5848, 6735, 2951, 3583, 3752, 0, 2701, 6136, 6047, 4179, 3184, 4990, 1776, 2015, 4756, 4400, 4733, 1665, 3399, 0, 3920, 1556, 3239, 5927, 1193, 4077, 4066, 4879, 5952, 2610, 3674, 0, 1682, 6139, 10994, 2262, 2315, 9710, 11296, 0, 12443, 4378, 6221, 8424, 7789, 1346, 0, 6840, 5808, 15893, 3310, 14216, 0, 5480, 1790, 2085, 3623, 3286, 4700, 3996, 2913, 2367, 1725, 5204, 2311, 2965, 3593, 0, 24055, 13551, 0, 11158, 6005, 13660, 11402, 10202, 0, 7769, 4788, 1884, 7859, 1587, 2695, 4885, 1651, 3921, 4647, 1109, 0, 5356, 8571, 5279, 2408, 0, 4523, 5592, 7243, 6911, 7604, 4000, 3415, 7335, 7325, 6703, 7012, 0, 5293, 6269, 5782, 6615, 4499, 7453, 6217, 5074, 7079, 7098, 6023, 6796, 0, 4735, 4908, 5414, 2580, 2794, 2243, 6211, 5507, 2794, 5024, 6115, 3177, 3466, 3455, 0, 4725, 1786, 2451, 4178, 3485, 1208, 2228, 4479, 2207, 4882, 4332, 3857, 3771, 5319, 0, 1401, 14031, 1695, 0, 1921, 9783, 5635, 1786, 10360, 6850, 4863, 1404, 0, 2442, 16957, 12686, 0, 4039, 5926, 5272, 5775, 6138, 7024, 6142, 6641, 4558, 5609, 7398, 2347, 0, 23477, 2485, 7786, 0, 5340, 1527, 1952, 2863, 2246, 5007, 6093, 3073, 3193, 4766, 5291, 2878, 2585, 6225, 0, 5259, 6647, 2722, 4293, 4990, 5668, 5620, 1183, 2420, 6872, 0, 1598, 6291, 8717, 1640, 8729, 6411, 1479, 7903, 0, 5887, 9297, 5108, 4814, 3171, 10077, 3700, 9785, 0, 5500, 6377, 2407, 8051, 4278, 2402, 2098, 5988, 2301, 4956, 2267, 0, 1802, 5166, 5094, 1190, 5493, 1562, 4255, 2126, 1959, 4176, 5354, 2921, 2743, 5640, 3116, 0, 11346, 12151, 12510, 11039, 11673, 7320, 0, 3029, 6031, 4235, 4697, 2645, 6612, 6585, 2072, 5350, 3869, 1793, 4184, 4684, 0, 6720, 6848, 1173, 5192, 2683, 4863, 6494, 2116, 2334, 2428, 3922, 5454, 4604, 0, 7695, 2885, 4466, 5049, 8098, 4177, 6464, 7981, 3183, 3346, 0, 5863, 3390, 10072, 4163, 9577, 6662, 5975, 8122, 0, 1443, 4466, 7142, 6107, 1032, 3545, 4362, 8074, 1339, 2477, 1322, 0, 1912, 14613, 15225, 16363, 0, 4119, 1645, 8059, 7384, 5633, 11876, 5144, 0, 2886, 7293, 17062, 0, 1344, 5571, 6367, 2730, 1134, 5853, 4098, 6827, 1283, 1437, 6932, 3271, 0, 3847, 1889, 6732, 1468, 1087, 3477, 5090, 3164, 5436, 6696, 0, 11985, 4877, 12181, 3096, 7222, 0, 12716, 11377, 11278, 1601, 0, 5418, 11900, 5334, 8971, 10651, 7907, 11469, 0, 6907, 7969, 2738, 3250, 4497, 5563, 2339, 7091, 2032, 0, 1092, 8088, 6222, 8095, 6713, 3648, 2551, 1956, 3413, 8164, 0, 6511, 6142, 4365, 4237, 6568, 1832, 5450, 3012, 3588, 2699, 4931, 0, 32059, 19019, 0, 2627, 8198, 10858, 11115, 1648, 2383, 0, 9821, 7551, 1459, 6217, 10094, 1445, 9978, 0, };