n=500;
m=100;
T=[3512, 2145, 3757, 9889, 5195, 3886, 2116, 6257, 2812, 4523, 6217, 4559, 2275, 6562, 2627, 5425, 1181, 949, 38, 9588, 9366, 5440, 6158, 1614, 4417, 3376, 8117, 5375, 2759, 971, 7239, 1705, 2590, 9546, 467, 3731, 6092, 6340, 4764, 4737, 8228, 7810, 4159, 7623, 5254, 3806, 6942, 2591, 232, 4281, 3012, 4697, 4964, 5552, 8763, 3964, 4776, 1458, 1987, 1359, 9672, 8027, 6523, 1278, 2358, 4914, 2513, 487, 1414, 8303, 2237, 1537, 5394, 3230, 7928, 6046, 4495, 1002, 2314, 9012, 8415, 5254, 7618, 360, 9764, 5153, 1323, 9049, 6625, 7393, 2470, 66, 5486, 7191, 6064, 8062, 913, 5913, 7080, 3292, 5312, 1855, 1855, 3718, 2500, 3241, 1762, 8506, 4216, 853, 9598, 6390, 3667, 477, 1609, 1273, 5222, 3529, 9333, 3921, 322, 89, 1042, 5686, 5879, 306, 942, 1351, 4931, 1397, 2771, 9647, 3650, 4995, 6442, 601, 791, 6741, 3733, 41, 8834, 3636, 5904, 3027, 3752, 1932, 9512, 3499, 5873, 6799, 1278, 6211, 9985, 3351, 7641, 1756, 632, 5751, 1722, 3374, 2302, 4931, 7846, 7539, 7048, 2049, 7206, 1232, 5718, 4065, 4378, 1754, 5126, 9230, 4605, 1489, 3931, 8245, 3213, 710, 2174, 9803, 7247, 8668, 4057, 1307, 9526, 1242, 1113, 2644, 4908, 7550, 8002, 2856, 8241, 1804, 7369, 2993, 2015, 4557, 4254, 974, 18, 7458, 3591, 3434, 1612, 4177, 6134, 9154, 264, 1528, 1499, 3357, 5419, 2918, 3929, 2187, 718, 6817, 3675, 753, 3172, 5322, 3311, 5935, 9801, 5758, 2819, 3374, 5129, 1415, 3175, 4854, 326, 7740, 4179, 8135, 7700, 1667, 9479, 5879, 4319, 1511, 8828, 1305, 4300, 9187, 1457, 2108, 6595, 4699, 5597, 2549, 6580, 3268, 2734, 3022, 3366, 7330, 3093, 7470, 1086, 4264, 9126, 7169, 8371, 4468, 693, 3961, 2423, 8014, 1546, 4460, 5497, 687, 9875, 4620, 8695, 5781, 4325, 3844, 3644, 4759, 4821, 1969, 4743, 6372, 4401, 2092, 7263, 4754, 4054, 3704, 7824, 6963, 8272, 7876, 1252, 4645, 9272, 3165, 5952, 6985, 3768, 830, 8875, 8650, 2402, 3308, 4027, 7924, 2574, 3149, 9025, 4229, 5065, 6716, 7952, 4377, 1255, 4969, 2967, 2240, 6940, 5027, 5791, 2837, 5419, 5217, 926, 9105, 1177, 8050, 9487, 1434, 5768, 3421, 8752, 3879, 3661, 8601, 7917, 2019, 5385, 5184, 2394, 2856, 7890, 1410, 2673, 2942, 4359, 5304, 7025, 8551, 2698, 6766, 4701, 9715, 3110, 6455, 4363, 8280, 1885, 4249, 6299, 6523, 2049, 2067, 2937, 5561, 4665, 4515, 381, 5166, 371, 6350, 4026, 2202, 5797, 8907, 2558, 1401, 9983, 5513, 5804, 6581, 9888, 2753, 5995, 8539, 6912, 8226, 2883, 9407, 6667, 2591, 3281, 5229, 6007, 6699, 2556, 1095, 8670, 7541, 7736, 2676, 8970, 4077, 6330, 1880, 6467, 2796, 947, 447, 3380, 6178, 9417, 6362, 3603, 5235, 3789, 2738, 1029, 6857, 5178, 2312, 4632, 8697, 3453, 5688, 515, 608, 4877, 4845, 7100, 6214, 2107, 6647, 9647, 8359, 4103, 3557, 7725, 1893, 2298, 3851, 206, 3612, 6031, 795, 172, 2491, 1166, 472, 9265, 5006, 1639, 3836, 3136, 8901, 7108, 8160, 5636, 5052, 124, 6140, 6067, 7296, 419, 524, 5642, 9357, 8939, 5322, 1960, 9583, 891, 6341, 7669, 8457, 891, 4879, 7369, 1033, 5015, 6200, 6272, 6985, 3023, 5123, 6279, 2054, 2629, 1085, 5671, 4117, 3037, 8888];