# input import sys input = sys.stdin.readline II = lambda : int(input()) MI = lambda : map(int, input().split()) LI = lambda : [int(a) for a in input().split()] SI = lambda : input().rstrip() LLI = lambda n : [[int(a) for a in input().split()] for _ in range(n)] LSI = lambda n : [input().rstrip() for _ in range(n)] MI_1 = lambda : map(lambda x:int(x)-1, input().split()) LI_1 = lambda : [int(a)-1 for a in input().split()] mod = 998244353 inf = 1001001001001001001 ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97 ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97 yes = lambda : print("Yes") no = lambda : print("No") yn = lambda flag : print("Yes" if flag else "No") prinf = lambda ans : print(ans if ans < 1000001001001001001 else -1) alplow = "abcdefghijklmnopqrstuvwxyz" alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)} DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]] DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]] DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]] prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59] sys.set_int_max_str_digits(0) # sys.setrecursionlimit(10**6) # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') from collections import defaultdict,deque from heapq import heappop,heappush from bisect import bisect_left,bisect_right DD = defaultdict BSL = bisect_left BSR = bisect_right p = 2503 # a = [] # for i in range(p - 1): # a.append(i + (p - 1) * ((i - pow(3, i, p)) % p)) # for i in range(1, 5000): # b = [(x * i) % (p * (p - 1)) for x in a] # b.sort() # ok = [0] * (p - 1) # for i in range(p - 1): # x = (b[(i+99) % (p - 1)] - b[i]) % (p * (p - 1)) # if x <= 3 * 10 ** 5: # ok[i] = 1 # s = None # for i in range(p - 1): # if all(ok[i % (p - 1)] for i in range(i, i + 2500)): # s = i # break # if s != None: # break # print(s, b) b = [2289, 3225, 8739, 13437, 18370, 18774, 21165, 24883, 24970, 27298, 30320, 31988, 39785, 40238, 41163, 45415, 46207, 52784, 54063, 55612, 58592, 63652, 67214, 67410, 68551, 69338, 70875, 72793, 74203, 74820, 75405, 77655, 78236, 78613, 78658, 83497, 83878, 84681, 86461, 88353, 92189, 93656, 95107, 96524, 98790, 99378, 100751, 102175, 107932, 108148, 108160, 110244, 112029, 116022, 116204, 118422, 120223, 121755, 122655, 124617, 125924, 127022, 127798, 128197, 131079, 132881, 134472, 135995, 136407, 138999, 140259, 142648, 144279, 147336, 148307, 149794, 154583, 155030, 155877, 157349, 158591, 160037, 162666, 163069, 164555, 166693, 167435, 167898, 169157, 169574, 171364, 174251, 180432, 180784, 185696, 188613, 197852, 198316, 199073, 201637, 201834, 202961, 203999, 204210, 210214, 210858, 221663, 223206, 227313, 232543, 233166, 234456, 236531, 247547, 247585, 248621, 248876, 251600, 254789, 257092, 257212, 261514, 263143, 264037, 267629, 268424, 270579, 271295, 271696, 274926, 275354, 280482, 281143, 281200, 284255, 285254, 286086, 288717, 289403, 289609, 290536, 296267, 299743, 301952, 303519, 305827, 306534, 307514, 309056, 310446, 312455, 318358, 319982, 322866, 325517, 327415, 329361, 331621, 332396, 332540, 334283, 336162, 337030, 343528, 345597, 345863, 347766, 347989, 355798, 356998, 357912, 359319, 360874, 361664, 364524, 365171, 366472, 366562, 370601, 374212, 381129, 384059, 390503, 391373, 396568, 397097, 401077, 406037, 407063, 407395, 408094, 411280, 418333, 418413, 420111, 420605, 420989, 425890, 425961, 427615, 438469, 439309, 441772, 443231, 448334, 448701, 449917, 450471, 451601, 453917, 454618, 454890, 455859, 457088, 458110, 463678, 469410, 472305, 475724, 479657, 482188, 482388, 484860, 489458, 493601, 493977, 497912, 499389, 500513, 501032, 503188, 504120, 505098, 506603, 510065, 512031, 512252, 516440, 516459, 517941, 518557, 520074, 532559, 533765, 535016, 536036, 539216, 539823, 540815, 541421, 549163, 566272, 569346, 570586, 572848, 575283, 580300, 585713, 586459, 588738, 589838, 592649, 593097, 599481, 601472, 604386, 607241, 607245, 614453, 617568, 620681, 626040, 627410, 630476, 632644, 635711, 639026, 640104, 643231, 649841, 651973, 653015, 654941, 656958, 663006, 663997, 664095, 670401, 671537, 672033, 677175, 681167, 681192, 683730, 684335, 685951, 686259, 686437, 687934, 691052, 693227, 693330, 694063, 694767, 696644, 697753, 700092, 700393, 701943, 708392, 709495, 719633, 719781, 723400, 726145, 729662, 731665, 731772, 731832, 734743, 741331, 742454, 748763, 750999, 753684, 757266, 759400, 760036, 760650, 761492, 765755, 766838, 769516, 771154, 772301, 773170, 773609, 775802, 776222, 778644, 780335, 781109, 781619, 783563, 783597, 788035, 788088, 798974, 801137, 802467, 802934, 803702, 803863, 809782, 810794, 821961, 824545, 829291, 829296, 829676, 831945, 834654, 838384, 838819, 839637, 848922, 849304, 855088, 857918, 867767, 868795, 873064, 875118, 877809, 890552, 891065, 895293, 897188, 897786, 899127, 903642, 904130, 904184, 906670, 907609, 911654, 914223, 916940, 916942, 917099, 918337, 921263, 925193, 925482, 925614, 931727, 934466, 946637, 946801, 947245, 948144, 948650, 951448, 953202, 958423, 963671, 965743, 966557, 967539, 968986, 971357, 973653, 974818, 977354, 982697, 984013, 986330, 988478, 991636, 993075, 993744, 995896, 999402, 1006416, 1007691, 1007949, 1009377, 1009741, 1009907, 1016868, 1017019, 1018148, 1028877, 1028935, 1036122, 1041864, 1042809, 1045552, 1054074, 1056726, 1061226, 1063189, 1066756, 1068098, 1069531, 1073904, 1076329, 1076338, 1077475, 1078798, 1080415, 1081497, 1083620, 1083646, 1085745, 1089957, 1094319, 1094678, 1095390, 1095748, 1096256, 1098452, 1098808, 1109250, 1111754, 1115825, 1118219, 1124190, 1126671, 1127036, 1127974, 1128372, 1128385, 1128388, 1128509, 1128592, 1128664, 1129581, 1130344, 1134152, 1135513, 1136984, 1137438, 1138215, 1138543, 1140252, 1146749, 1151325, 1151550, 1152220, 1153216, 1158651, 1163965, 1165358, 1166322, 1166520, 1167740, 1169928, 1173074, 1174928, 1175335, 1176547, 1179277, 1183381, 1184561, 1185275, 1187611, 1188118, 1193322, 1194639, 1194923, 1197303, 1199814, 1200224, 1201763, 1204142, 1204635, 1208216, 1208567, 1209295, 1215313, 1219315, 1220796, 1223179, 1224034, 1224225, 1225738, 1228040, 1233227, 1234787, 1236440, 1237177, 1239951, 1239971, 1240664, 1241771, 1243234, 1243516, 1244763, 1246509, 1247507, 1248119, 1249313, 1250272, 1253709, 1254649, 1255453, 1257532, 1261369, 1261478, 1262098, 1265876, 1277139, 1278260, 1282109, 1283064, 1283551, 1287071, 1290408, 1294855, 1296101, 1298534, 1304797, 1305524, 1315817, 1316403, 1319713, 1325409, 1327679, 1331731, 1334347, 1334896, 1336575, 1337496, 1342028, 1349503, 1350988, 1353717, 1355980, 1356284, 1360225, 1361999, 1363750, 1364180, 1364333, 1365181, 1366462, 1372749, 1377429, 1380162, 1384477, 1384563, 1385619, 1388163, 1394737, 1395969, 1398749, 1400717, 1406374, 1408305, 1408879, 1416183, 1419223, 1421128, 1427859, 1428527, 1428621, 1429770, 1430148, 1432512, 1434488, 1439358, 1439627, 1439741, 1442838, 1445836, 1449873, 1461838, 1462538, 1465288, 1469368, 1470352, 1473169, 1473319, 1473403, 1476300, 1476673, 1477066, 1481228, 1484141, 1495825, 1495872, 1498475, 1500912, 1501164, 1501866, 1505678, 1507855, 1510271, 1512626, 1513716, 1519526, 1520952, 1525098, 1529621, 1536042, 1536150, 1540666, 1540946, 1542878, 1544286, 1548096, 1548568, 1550437, 1552950, 1554338, 1556864, 1558843, 1567276, 1572225, 1574883, 1579219, 1579518, 1580075, 1583013, 1583704, 1584792, 1586600, 1587242, 1587385, 1593570, 1594858, 1597506, 1597594, 1600209, 1602972, 1603187, 1604343, 1606218, 1607862, 1609045, 1611392, 1612425, 1612908, 1616383, 1617056, 1618412, 1618518, 1618631, 1619276, 1622482, 1624345, 1628499, 1630171, 1630346, 1630383, 1635169, 1635341, 1636599, 1637768, 1639041, 1639339, 1641240, 1642202, 1647573, 1651435, 1654254, 1656199, 1658522, 1662347, 1664414, 1667357, 1669908, 1670077, 1670451, 1676814, 1678196, 1678386, 1678401, 1680026, 1684047, 1691230, 1691278, 1693092, 1693321, 1693999, 1694362, 1694805, 1696160, 1702860, 1706651, 1716255, 1718356, 1722170, 1722308, 1728055, 1729969, 1733541, 1733666, 1734079, 1734538, 1736795, 1739357, 1745373, 1754388, 1759603, 1761003, 1774138, 1774322, 1777156, 1777969, 1780586, 1784671, 1785042, 1788365, 1788740, 1791178, 1795878, 1796268, 1798097, 1803566, 1805962, 1812695, 1814467, 1817274, 1821814, 1823625, 1828231, 1828564, 1829333, 1839783, 1840488, 1843038, 1845888, 1846480, 1849857, 1852701, 1854986, 1854993, 1858496, 1861550, 1862623, 1866907, 1867648, 1868067, 1868541, 1869061, 1869713, 1870289, 1872169, 1873662, 1877691, 1878243, 1878318, 1883667, 1885966, 1888168, 1893970, 1894237, 1900933, 1906831, 1917432, 1917766, 1921831, 1927320, 1931181, 1932781, 1936939, 1940765, 1941240, 1943499, 1943523, 1948786, 1957090, 1958653, 1961227, 1963640, 1967624, 1970376, 1970416, 1972852, 1973364, 1973725, 1976598, 1977023, 1980993, 1982358, 1982611, 1985550, 1990966, 1997869, 1998926, 1999055, 2001047, 2001343, 2002158, 2003534, 2007745, 2009065, 2020336, 2020599, 2021227, 2034613, 2037201, 2037350, 2040485, 2041601, 2041989, 2045142, 2045866, 2046431, 2047585, 2048247, 2051440, 2053139, 2055508, 2056756, 2057992, 2062277, 2062686, 2070011, 2084103, 2091790, 2095989, 2096413, 2100220, 2100731, 2102404, 2107698, 2111207, 2112622, 2117182, 2118199, 2121233, 2123710, 2127800, 2132433, 2132913, 2133500, 2133630, 2136969, 2144292, 2146766, 2147257, 2147723, 2149967, 2153652, 2154792, 2160356, 2160542, 2163124, 2169672, 2172067, 2173894, 2173971, 2178466, 2179050, 2179688, 2182852, 2184583, 2186818, 2188483, 2189830, 2189860, 2191583, 2191831, 2192068, 2197394, 2197766, 2198689, 2200298, 2202556, 2207578, 2208371, 2211981, 2217037, 2217506, 2224327, 2225211, 2236353, 2239265, 2240806, 2247116, 2248505, 2251929, 2255673, 2259932, 2262469, 2264429, 2265161, 2267151, 2271622, 2274069, 2276665, 2277206, 2277216, 2282058, 2284443, 2287695, 2294590, 2298566, 2298705, 2300850, 2301375, 2301893, 2317990, 2319215, 2319602, 2321707, 2324712, 2327484, 2327719, 2331078, 2333560, 2336347, 2337297, 2337821, 2342979, 2343635, 2348103, 2351047, 2353354, 2356571, 2360609, 2363332, 2363778, 2364338, 2367424, 2380024, 2380466, 2384096, 2384403, 2384834, 2384907, 2388290, 2390138, 2392510, 2396608, 2401212, 2403245, 2409355, 2411376, 2411417, 2412981, 2414526, 2418980, 2420548, 2422900, 2428292, 2429086, 2432124, 2432699, 2435476, 2436469, 2438114, 2439897, 2440200, 2443196, 2448782, 2449488, 2451934, 2453346, 2453412, 2454629, 2457069, 2458435, 2461935, 2462574, 2466225, 2469014, 2473013, 2477920, 2480187, 2481122, 2483886, 2484346, 2486057, 2487441, 2489273, 2489370, 2504944, 2505659, 2507423, 2515670, 2516939, 2521081, 2524321, 2527248, 2535658, 2536698, 2538386, 2538730, 2539052, 2539739, 2539956, 2542334, 2553827, 2561136, 2561454, 2565166, 2565639, 2566448, 2566816, 2567948, 2568463, 2571546, 2571688, 2573136, 2575336, 2578665, 2579414, 2579616, 2580399, 2580562, 2580855, 2581458, 2586234, 2587111, 2589020, 2597465, 2599476, 2601354, 2601622, 2602524, 2606866, 2611702, 2611938, 2615159, 2615285, 2616172, 2618395, 2627367, 2629592, 2630318, 2632521, 2633692, 2634027, 2634373, 2635647, 2635957, 2637146, 2637667, 2642646, 2643865, 2648598, 2650090, 2658508, 2659159, 2661897, 2665535, 2667846, 2671732, 2674887, 2679819, 2682785, 2684566, 2686192, 2686406, 2690449, 2698152, 2701440, 2701684, 2703425, 2704509, 2705018, 2708065, 2713896, 2715614, 2716799, 2719026, 2721344, 2721884, 2723415, 2723853, 2728108, 2728534, 2732769, 2734066, 2739691, 2740581, 2744283, 2748474, 2751393, 2754615, 2757206, 2761264, 2763332, 2767247, 2776169, 2780336, 2781517, 2784235, 2786363, 2786548, 2794001, 2794850, 2796862, 2800598, 2800801, 2804642, 2805219, 2809670, 2811700, 2812089, 2815442, 2815623, 2816894, 2817177, 2818762, 2824073, 2830684, 2831750, 2832063, 2836413, 2837229, 2838961, 2842131, 2843995, 2844751, 2845072, 2845574, 2850229, 2850329, 2855436, 2855983, 2858389, 2859805, 2861324, 2861724, 2865105, 2865852, 2869695, 2872714, 2875599, 2875734, 2876406, 2879744, 2885130, 2885166, 2888426, 2888987, 2893138, 2904206, 2911530, 2912058, 2913786, 2914482, 2917616, 2919512, 2920851, 2923365, 2926652, 2926806, 2928417, 2929038, 2930360, 2940656, 2941530, 2941883, 2942562, 2949257, 2951400, 2953801, 2957234, 2958772, 2962300, 2967665, 2976155, 2976379, 2977635, 2978232, 2981923, 2984480, 2987524, 2988359, 2988892, 2989283, 2992901, 2999619, 2999742, 3000400, 3018347, 3019953, 3022979, 3023529, 3025363, 3027638, 3028238, 3032406, 3034588, 3034904, 3036879, 3039230, 3042139, 3042616, 3042662, 3045531, 3048030, 3051335, 3054426, 3056787, 3072302, 3073000, 3074304, 3081356, 3083903, 3087999, 3088244, 3090102, 3098641, 3098952, 3101587, 3116132, 3117551, 3117643, 3119458, 3127965, 3128566, 3129912, 3140576, 3145069, 3148803, 3151315, 3151660, 3152336, 3152759, 3152850, 3153350, 3153894, 3154209, 3154509, 3157533, 3158049, 3158809, 3159146, 3160353, 3161811, 3162140, 3162446, 3162464, 3170845, 3175496, 3177783, 3184241, 3185306, 3188052, 3191332, 3192299, 3192866, 3195915, 3196418, 3203131, 3203236, 3206645, 3211447, 3214571, 3230561, 3230788, 3235134, 3236268, 3236448, 3238746, 3239861, 3244601, 3247672, 3252225, 3253668, 3254352, 3260383, 3260642, 3261301, 3266321, 3266543, 3267753, 3273756, 3286219, 3290539, 3291336, 3291940, 3292785, 3292998, 3293701, 3293940, 3297945, 3301211, 3304064, 3312073, 3312826, 3314161, 3315901, 3319157, 3323907, 3326994, 3330268, 3330637, 3337184, 3340391, 3341836, 3349035, 3350690, 3352697, 3352741, 3355274, 3357770, 3361176, 3364153, 3364508, 3364726, 3365559, 3365674, 3365834, 3366393, 3367699, 3371888, 3372912, 3374706, 3375436, 3379355, 3385616, 3387312, 3390393, 3390489, 3395339, 3398464, 3404097, 3405857, 3411199, 3418145, 3424601, 3427021, 3430845, 3431900, 3432620, 3434701, 3435896, 3436682, 3437331, 3439984, 3442306, 3446104, 3448299, 3449287, 3451024, 3452707, 3458634, 3458842, 3459889, 3464052, 3465005, 3467011, 3468112, 3468674, 3473915, 3476132, 3477277, 3482727, 3483021, 3486372, 3487497, 3490492, 3493273, 3498613, 3501215, 3503167, 3511760, 3512384, 3513272, 3514825, 3519156, 3525742, 3526703, 3532510, 3534562, 3535495, 3547392, 3549741, 3555973, 3556101, 3557629, 3560921, 3565745, 3566895, 3571956, 3572502, 3573019, 3574324, 3574858, 3578072, 3579942, 3581282, 3584947, 3586520, 3591085, 3597628, 3600329, 3603169, 3606426, 3607847, 3608586, 3609081, 3613909, 3617011, 3617591, 3618155, 3621374, 3623703, 3625547, 3625798, 3627610, 3630163, 3633671, 3637506, 3637996, 3639591, 3640027, 3642781, 3645782, 3646792, 3647979, 3649783, 3656664, 3657314, 3658906, 3662988, 3665347, 3666662, 3671172, 3677050, 3681194, 3681200, 3683082, 3690696, 3691640, 3692242, 3696896, 3697647, 3702315, 3706249, 3708651, 3710387, 3711297, 3711298, 3713356, 3713922, 3715962, 3718777, 3722542, 3723047, 3723312, 3726023, 3726876, 3728027, 3729698, 3731487, 3732331, 3733192, 3735927, 3737900, 3738001, 3739063, 3740394, 3743841, 3743906, 3753164, 3754240, 3755644, 3756237, 3758831, 3760140, 3764348, 3770501, 3770837, 3770916, 3771768, 3772010, 3778665, 3779963, 3788952, 3789063, 3793284, 3793749, 3798463, 3801423, 3801945, 3803687, 3806520, 3807319, 3809781, 3811652, 3811995, 3812820, 3813147, 3814018, 3819124, 3819579, 3823504, 3824275, 3827283, 3828055, 3829881, 3833304, 3836434, 3836665, 3836912, 3838771, 3839530, 3839776, 3844903, 3846111, 3856498, 3858648, 3858741, 3860251, 3861258, 3864182, 3864961, 3866025, 3866596, 3868926, 3873446, 3875608, 3875962, 3876057, 3886095, 3894607, 3901946, 3902835, 3903214, 3904565, 3904888, 3906142, 3906273, 3917271, 3918055, 3918234, 3922443, 3924842, 3924869, 3926256, 3926819, 3926887, 3927513, 3927665, 3929428, 3930245, 3934550, 3937277, 3940249, 3941906, 3947860, 3953468, 3954128, 3962295, 3962490, 3962831, 3964123, 3966309, 3967845, 3975763, 3979939, 3980470, 3984443, 3984631, 3988925, 3994464, 3995053, 3995138, 3998280, 4005077, 4005931, 4006114, 4007306, 4007358, 4018019, 4019785, 4020274, 4020911, 4021959, 4022135, 4022933, 4024071, 4027839, 4029503, 4034850, 4037691, 4041228, 4046202, 4046608, 4048311, 4048565, 4049133, 4051439, 4054817, 4055787, 4056791, 4057262, 4059781, 4060972, 4062996, 4064214, 4064370, 4064767, 4065704, 4068014, 4068264, 4069251, 4073338, 4075856, 4078171, 4080559, 4080871, 4085231, 4087098, 4088553, 4091006, 4091337, 4092278, 4104062, 4104070, 4107044, 4108093, 4108357, 4112021, 4118272, 4120743, 4121942, 4122251, 4122538, 4127687, 4128566, 4132175, 4132883, 4134317, 4140088, 4142319, 4144955, 4145709, 4149258, 4149529, 4151578, 4155491, 4157183, 4157525, 4163227, 4163344, 4173055, 4174988, 4177750, 4177991, 4180296, 4183626, 4185025, 4185974, 4188264, 4193055, 4197104, 4197923, 4214634, 4217750, 4219071, 4219505, 4220540, 4220601, 4222595, 4225433, 4226948, 4228697, 4234839, 4234870, 4235071, 4238666, 4242033, 4245190, 4245504, 4248781, 4254801, 4255796, 4260725, 4264284, 4265460, 4268270, 4269037, 4269153, 4269362, 4269692, 4284939, 4287482, 4288643, 4289291, 4289365, 4289921, 4290479, 4296982, 4300693, 4305907, 4307159, 4308337, 4309219, 4309648, 4314409, 4314771, 4322292, 4323728, 4325756, 4329520, 4330131, 4332720, 4335276, 4346656, 4350279, 4352017, 4362541, 4368733, 4373071, 4374971, 4375022, 4376382, 4376673, 4376843, 4377593, 4377648, 4383678, 4385483, 4386687, 4388239, 4390209, 4390343, 4392549, 4392582, 4396798, 4398674, 4402738, 4403685, 4407337, 4408443, 4409582, 4413825, 4414637, 4415759, 4416151, 4418133, 4423438, 4424276, 4425086, 4427230, 4428810, 4428946, 4430796, 4431156, 4431453, 4433489, 4439571, 4440050, 4440598, 4445553, 4447783, 4449286, 4449516, 4449966, 4450585, 4452822, 4454220, 4454963, 4461839, 4462720, 4476144, 4477302, 4478084, 4478767, 4479733, 4481105, 4481454, 4481687, 4486305, 4492536, 4496163, 4499119, 4499389, 4506283, 4507736, 4509119, 4516420, 4523400, 4531556, 4535312, 4537566, 4543980, 4546817, 4548858, 4549780, 4553664, 4554304, 4554643, 4555124, 4557421, 4558784, 4559416, 4560491, 4563728, 4567162, 4571346, 4572610, 4575284, 4579830, 4582709, 4583546, 4583720, 4586334, 4586393, 4588151, 4590892, 4592010, 4602164, 4602604, 4604343, 4607327, 4611078, 4612422, 4618829, 4621985, 4622179, 4622584, 4624394, 4628122, 4628470, 4631811, 4635815, 4645498, 4648194, 4650111, 4653193, 4655011, 4658782, 4660564, 4660627, 4663748, 4667143, 4671175, 4671930, 4672756, 4673935, 4677852, 4678109, 4678561, 4683615, 4684940, 4685868, 4690555, 4694208, 4695164, 4697691, 4699603, 4702055, 4703843, 4705482, 4706247, 4708235, 4720613, 4722420, 4722566, 4724653, 4724926, 4726017, 4730780, 4737189, 4740876, 4743635, 4743940, 4746810, 4749258, 4751091, 4751855, 4755397, 4756199, 4759104, 4759840, 4764594, 4765149, 4769174, 4772727, 4773640, 4777004, 4777735, 4778054, 4781295, 4782918, 4784717, 4784991, 4788896, 4790625, 4792050, 4793516, 4794541, 4796182, 4801644, 4804533, 4809444, 4809722, 4812002, 4815590, 4818098, 4827121, 4830131, 4839446, 4848152, 4848829, 4849741, 4851018, 4856237, 4858175, 4860832, 4860854, 4862315, 4870054, 4874072, 4874666, 4876439, 4879024, 4879492, 4880706, 4884862, 4902942, 4908261, 4912642, 4913473, 4914082, 4916101, 4916396, 4920517, 4933594, 4934942, 4938988, 4941135, 4943201, 4945271, 4949547, 4954382, 4954748, 4957945, 4960239, 4963383, 4965391, 4965741, 4966771, 4976506, 4979607, 4979796, 4979863, 4981785, 4983112, 4984327, 4993348, 4996148, 4997466, 4998559, 5003720, 5006776, 5007524, 5017710, 5019697, 5021827, 5023435, 5023539, 5025325, 5027792, 5029414, 5032240, 5035708, 5038513, 5041858, 5042003, 5046957, 5048681, 5048713, 5051946, 5053327, 5054002, 5057048, 5059458, 5064421, 5065634, 5065775, 5068382, 5068879, 5069411, 5076052, 5077068, 5079150, 5080482, 5081397, 5082295, 5082323, 5083103, 5083124, 5090242, 5090375, 5092033, 5095192, 5097779, 5103688, 5105414, 5108613, 5110660, 5115518, 5116520, 5126198, 5130081, 5130911, 5133483, 5135479, 5135647, 5136049, 5137067, 5138524, 5141303, 5145610, 5153364, 5155689, 5165818, 5167118, 5169303, 5170996, 5172789, 5174315, 5174905, 5175367, 5182537, 5183760, 5184627, 5186927, 5187039, 5188509, 5188966, 5189794, 5191649, 5201480, 5201642, 5204665, 5205081, 5208453, 5210123, 5210914, 5212242, 5215331, 5218554, 5223993, 5230511, 5233498, 5236143, 5243010, 5248011, 5250601, 5254215, 5254555, 5254925, 5257500, 5265742, 5265792, 5265806, 5265841, 5269241, 5271064, 5274740, 5277539, 5287898, 5289400, 5291061, 5297072, 5297150, 5300967, 5301504, 5306806, 5307378, 5310511, 5312914, 5316592, 5320319, 5321657, 5331191, 5332159, 5336271, 5338781, 5339083, 5340395, 5340940, 5341764, 5341781, 5344844, 5348539, 5351384, 5352289, 5354957, 5358973, 5359062, 5359172, 5361348, 5367628, 5368643, 5372536, 5380000, 5383847, 5385567, 5387336, 5390707, 5394743, 5396753, 5397448, 5400743, 5402137, 5403456, 5409292, 5417383, 5419077, 5425198, 5428911, 5432004, 5432637, 5439420, 5447020, 5447465, 5449364, 5449796, 5455303, 5456860, 5457803, 5458425, 5458663, 5460055, 5460752, 5462528, 5463458, 5464512, 5467009, 5470310, 5476883, 5477230, 5484631, 5485115, 5486378, 5494911, 5496024, 5497206, 5497801, 5501045, 5504421, 5504561, 5506989, 5507712, 5512355, 5514354, 5517252, 5524448, 5533287, 5534137, 5535815, 5536135, 5539777, 5540674, 5541328, 5544715, 5548136, 5550533, 5551215, 5554805, 5555095, 5555490, 5556691, 5558180, 5560206, 5563242, 5564150, 5564337, 5567326, 5568211, 5568824, 5572807, 5575476, 5576640, 5581085, 5581773, 5583334, 5584453, 5587559, 5588536, 5588559, 5592988, 5594298, 5597206, 5600690, 5601076, 5605149, 5605326, 5611314, 5613081, 5613518, 5617486, 5623933, 5625690, 5627184, 5630117, 5631983, 5637009, 5637347, 5638865, 5645400, 5645527, 5646510, 5648433, 5649553, 5650840, 5651830, 5652916, 5666144, 5667205, 5675734, 5676599, 5678641, 5679402, 5680043, 5681670, 5684918, 5688763, 5688845, 5689455, 5692041, 5693949, 5694235, 5695585, 5699708, 5701232, 5703895, 5706592, 5706852, 5707937, 5708689, 5711480, 5712147, 5716018, 5719221, 5719864, 5720836, 5720898, 5722800, 5723912, 5725486, 5726539, 5730113, 5730284, 5730913, 5731577, 5731973, 5739747, 5741571, 5743924, 5758627, 5762396, 5767914, 5768815, 5770291, 5777639, 5780169, 5783565, 5785716, 5785745, 5786033, 5786602, 5787078, 5787236, 5788715, 5789156, 5791498, 5793562, 5794013, 5794965, 5797923, 5802327, 5802797, 5804494, 5805021, 5805282, 5808491, 5812077, 5813058, 5813307, 5814018, 5815983, 5816064, 5818184, 5820077, 5820320, 5820821, 5829978, 5831554, 5834362, 5836477, 5836519, 5838081, 5839535, 5843506, 5845782, 5847379, 5848553, 5849462, 5851114, 5851957, 5852122, 5857455, 5858542, 5863055, 5863931, 5864208, 5864602, 5865035, 5865227, 5865453, 5867501, 5871627, 5872316, 5873196, 5877153, 5877275, 5877393, 5881125, 5883186, 5883256, 5885102, 5889858, 5890647, 5896537, 5897668, 5901014, 5903136, 5910049, 5910911, 5911817, 5916334, 5919049, 5923332, 5927198, 5927625, 5928792, 5933148, 5933794, 5936716, 5938810, 5943728, 5944391, 5946557, 5949308, 5953067, 5956233, 5961109, 5961830, 5964597, 5971815, 5975624, 5979182, 5980768, 5981626, 5985412, 5986137, 5989547, 5989590, 5993869, 5994665, 6002792, 6003768, 6004260, 6005033, 6005135, 6006795, 6017148, 6024572, 6025393, 6026138, 6028470, 6030921, 6031131, 6032417, 6037792, 6040210, 6040708, 6048982, 6053016, 6061102, 6061158, 6062983, 6065650, 6069852, 6071932, 6073457, 6074537, 6074945, 6075471, 6076206, 6077171, 6077629, 6083341, 6088517, 6089356, 6089503, 6091051, 6094406, 6094905, 6099639, 6102026, 6105874, 6107002, 6121502, 6121984, 6123217, 6123286, 6123951, 6126164, 6126490, 6129098, 6131986, 6132159, 6136455, 6137195, 6140132, 6145246, 6146603, 6150973, 6154309, 6154502, 6156602, 6160345, 6160384, 6174078, 6176894, 6178037, 6179105, 6180144, 6181406, 6196291, 6196576, 6197154, 6201132, 6203622, 6203633, 6208573, 6210215, 6213413, 6214316, 6220526, 6222644, 6223667, 6224246, 6226766, 6226885, 6231472, 6231734, 6235139, 6247285, 6248366, 6248442, 6248723, 6253557, 6256828, 6259249, 6262387] s = 0 n = II() # print(i) a = [] for i in range(2500): a.append((b[(s + i) % (p - 1)] - b[s]) % (p * (p - 1))) # print(i, s, a) g = [[0] * n for i in range(n)] for i in range(n): if i & 1: for j in range(n): g[i][j] = a[i*n + j] else: for j in range(n): g[i][~j] = a[i*n + j] for i in range(n - 1): a = [abs(g[i][j] - g[i+1][j]) for j in range(n)] print(*a) for i in range(n): a = [abs(g[i][j] - g[i][j+1]) for j in range(n - 1)] print(*a)