lista = [1, 3, 5, 2, 1, 10, 13, 19, 13, 45, 52, 105, 184, 243, 257, 276, 277, 286, 291, 303, 365, 451, 394, 376, 288, 255, 156, 138, 83, 27, -21, -117, -198, -246, -240, -163, -151, -135, -120, -38, 31, 36, 71, 83, 108, 157, 255, 319, 377, 427, 465, 484, 566, 637, 671, 729, 795, 809, 864, 873, 903, 997, 1022, 1114, 1178, 1255, 1324, 1375, 1439, 1486, 1579, 1634, 1639, 1663, 1677, 1741, 1784, 1807, 1825, 1924, 1906, 1897, 1827, 1781, 1699, 1689, 1634, 1571, 1479, 1438, 1434, 1388, 1328, 1276, 1207, 1119, 1116, 1025, 1011, 988, 910, 890, 839, 814, 794, 857, 921, 938, 976, 1015, 1017, 1090, 1095, 1174, 1265, 1330, 1353, 1393, 1440, 1485, 1517, 1525, 1440, 1341, 1249, 1217, 1213, 1132, 1079, 1040, 1032, 949, 939, 863, 796, 795, 741, 667, 570, 500, 490, 425, 335, 270, 181, 150, 57, -15, -79, -167, -186, -266, -280, -375, -468, -475, -537, -611, -688, -754, -761, -773, -859, -867, -870, -875, -902, -954, -988, -1040, -1056, -1144, -1129, -1042, -969, -880, -804, -752, -706, -650, -628, -601, -543, -512, -464, -455, -390, -330, -239, -152, -127, -95, -33, 28, 90, 143, 147, 221, 234, 332, 345, 379, 414, 503, 512, 539, 573, 644, 696, 716, 737, 802, 900, 941, 1013, 1081, 1160, 1227, 1210, 1123, 1052, 982, 909, 856, 828, 795, 720, 649, 603, 548, 502, 474, 455, 358, 295, 254, 164, 130, 48, -17, -49, -67, -29, 40, 121, 169, 188, 207, 257, 265, 279, 339, 394, 494, 559, 562, 577, 614, 577, 569, 483, 464, 395, 343, 338, 293, 241, 225, 149, 83, 6, -10, -57, -79, -123, -188, -208, -300, -341, -377, -431, -473, -573, -602, -611, -673, -731, -787, -805, -860, -901, -914, -957, -984, -1081, -1118, -1173, -1177, -1215, -1218, -1289, -1342, -1339, -1301, -1221, -1219, -1215, -1130, -1049, -977, -901, -856, -774, -769, -678, -632, -565, -525, -513, -438, -373, -333, -331, -314, -278, -247, -227, -206, -126, -120, -41, 44, 94, 137, 197, 115, 44, -17, -109, -200, -287, -378, -408, -486, -546, -630, -634, -670, -763, -823, -871, -875, -878, -964, -995, -1072, -1138, -1205, -1255, -1291, -1357, -1442, -1457, -1464, -1561, -1657, -1748, -1783, -1792, -1888, -1917, -1988, -2079, -2110, -2209, -2242, -2257, -2307, -2398, -2493, -2551, -2553, -2646, -2654, -2607, -2580, -2547, -2467, -2379, -2357, -2309, -2229, -2188, -2124, -2065, -1975, -1968, -1960, -1906, -1832, -1798, -1766, -1696, -1672, -1604, -1598, -1526, -1469, -1418, -1330, -1261, -1226, -1147, -1138, -1131, -1126, -1084, -1005, -979, -944, -884, -802, -726, -654, -625, -576, -482, -420, -397, -377, -329, -360, -392, -394, -439, -495, -531, -586, -616, -627, -628, -684, -765, -811, -832, -909, -913, -1003, -1062, -1096, -1162, -1232, -1319, -1387, -1476, -1556, -1624, -1664, -1667, -1622, -1607, -1521, -1425, -1334, -1285, -1256, -1238, -1144, -1046, -1018, -1086, -1146, -1245, -1284, -1375, -1402, -1485, -1572, -1589, -1649, -1665, -1693, -1766, -1859, -1906, -1947, -2007, -2077, -2115, -2170, -2246, -2252, -2335, -2341, -2359, -2397, -2413, -2473, -2548, -2639, -2727, -2751, -2840, -2887, -2935, -2976, -3015, -3105, -3184, -3265, -3328, -3421, -3422, -3394, -3348, -3269, -3210, -3171, -3087, -3025, -3104, -3126, -3211, -3262, -3288, -3318, -3331, -3359, -3439, -3532, -3568, -3623, -3719, -3764, -3836, -3888, -3911, -4003, -4080, -4125, -4131, -4194, -4238, -4304, -4393, -4448, -4496, -4505, -4530, -4583, -4663, -4730, -4745, -4843, -4886, -4945, -4986, -5053, -5138, -5215, -5245, -5252, -5345, -5314, -5282, -5264, -5229, -5129, -5083, -5069, -5045, -4950, -4858, -4852, -4777, -4748, -4687, -4669, -4575, -4568, -4474, -4440, -4423, -4350, -4311, -4247, -4214, -4126, -4065, -4000, -3926, -3908, -3853, -3808, -3771, -3757, -3718, -3671, -3660, -3598, -3535, -3440, -3418, -3401, -3394, -3392, -3378, -3381, -3446, -3519, -3600, -3658, -3698, -3703, -3739, -3837, -3903, -3937, -3979, -4002, -4062, -4079, -4143, -4148, -4179, -4260, -4316, -4377, -4402, -4449, -4461, -4466, -4552, -4589, -4631, -4703, -4774, -4850, -4868, -4883, -4947, -4948, -5022, -5080, -5116, -5124, -5168, -5213, -5234, -5292, -5328, -5286, -5226, -5208, -5147, -5095, -5072, -5034, -4956, -4949, -4914, -4955, -4965, -4992, -5053, -5089, -5105, -5167, -5187, -5226, -5300, -5329, -5419, -5496, -5547, -5624, -5650, -5750, -5803, -5890, -5908, -5928, -6020, -6085, -6128, -6135, -6175, -6180, -6187, -6212, -6214, -6289, -6319, -6291, -6219, -6123, -6095, -6031, -5941, -5914, -5864, -5808, -5715, -5689, -5630, -5562, -5476, -5387, -5302, -5242, -5171, -5096, -5030, -5014, -5011, -4968, -4961, -4911, -4908, -4841, -4822, -4767, -4716, -4658, -4575, -4507, -4411, -4311, -4228, -4194, -4132, -4053, -4005, -3939, -3883, -3794, -3739, -3661, -3616, -3662, -3671, -3736, -3763, -3823, -3866, -3876, -3897, -3912, -3954, -3964, -3971, -4041, -4054, -4150, -4243, -4288, -4319, -4389, -4441, -4459, -4489, -4532, -4545, -4593, -4657, -4620, -4599, -4569, -4512, -4465, -4462, -4422, -4356, -4291, -4244, -4167, -4154, -4102, -4076, -4028, -4005, -3923, -3899, -3904, -3985, -4008, -4044, -4102, -4187, -4222, -4263, -4353, -4449, -4543, -4563, -4596, -4590, -4534, -4454, -4394, -4342, -4293, -4231, -4198, -4125, -4122, -4121, -4062, -4009, -3950, -3852, -3841, -3809, -3759, -3703, -3611, -3570, -3476, -3412, -3342, -3272, -3204, -3178, -3147, -3121, -3050, -2973, -2875, -2847, -2756, -2717, -2647, -2630, -2610, -2564, -2614, -2654, -2688, -2692, -2719, -2794, -2818, -2871, -2958, -3035, -2998, -2958, -2881, -2824, -2780, -2769, -2673, -2620, -2526, -2500, -2475, -2405, -2381, -2349, -2348, -2260, -2255, -2223, -2151, -2078, -2039, -2026, -1963, -1867, -1792, -1721, -1633, -1564, -1488, -1402, -1305, -1247, -1200, -1184, -1128, -1048, -997, -961, -868, -768, -710, -662, -588, -494, -414, -320, -317, -288, -263, -226, -283, -337, -413, -482, -491, -518, -560, -594, -690, -691, -699, -710, -764, -827, -899, -960, -967, -990, -996, -1013, -1069, -1014, -965, -922, -875, -862, -839, -753, -657, -560, -476, -417, -412, -342, -307, -270, -200, -131, -94, -47, 1, 26, 90, 106, 193, 276, 328, 367, 425, 461, 501, 558, 567, 653, 735, 792, 797, 848, 853, 858, 905, 932, 946, 969, 992, 1002, 970, 959, 859, 830, 737, 662, 572, 549, 484, 415, 372, 310, 258, 172, 76, 9, 10, 25, 71, 76, 161, 258, 358, 416, 498, 512, 551, 632, 668, 751, 793, 832, 931, 1012, 1048, 1089, 1100, 1178, 1266, 1309, 1356, 1358, 1441, 1463, 1560, 1652, 1719, 1737, 1784, 1875, 1949, 1974, 1998, 2073, 2164, 2231, 2331, 2430, 999]