a := (1, 370)( 2,1333)(   3, 364)(   4, 955)(   5,2168)(   6,1176)
(   7,2058)(   8,  27)(   9, 293)(  10, 907)(  11, 457)(  12, 477)
(  13, 451)(  14,1922)(  15,  29)(  16,1464)(  17, 676)(  18, 289)
(  19, 732)(  20,1443)(  21,1306)(  22, 180)(  23,1129)(  24,  37)
(  25, 128)(  26, 334)(  28,1519)(  30, 793)(  31,1236)(  32, 367)
(  33,1399)(  34, 162)(  35,1938)(  36,1933)(  38, 187)(  39, 174)
(  40,1209)(  41,1730)(  42,1610)(  43,  70)(  44, 489)(  45, 329)
(  46,1383)(  47, 252)(  48,1114)(  49, 443)(  50,1555)(  51, 391)
(  52,1455)(  53,  95)(  54,1869)(  55, 299)(  56,1774)(  57, 338)
(  58, 554)(  59, 984)(  60,1790)(  61, 601)(  62,1762)(  63, 321)
(  64,1646)(  65, 844)(  66,2085)(  67, 416)(  68, 244)(  69, 129)
(  71, 166)(  72,1529)(  73,1010)(  74, 134)(  75,1921)(  76,1629)
(  77,1677)(  78,1195)(  79, 579)(  80,1250)(  81,2169)(  82,2167)
(  83,2106)(  84, 403)(  85,1523)(  86,1185)(  87, 295)(  88,1574)
(  89, 247)(  90,1189)(  92,1485)(  93, 138)(  94, 615)(  96, 572)
(  97,1298)(  98,1204)(  99,1748)( 100,1982)( 101,1812)( 102,2073)
( 103,1547)( 104, 520)( 105,1358)( 106,1261)( 107,1414)( 108, 469)
( 109, 701)( 110, 755)( 111,1263)( 112,1858)( 113,1278)( 114, 912)
( 115, 428)( 116, 934)( 117,1986)( 118,1419)( 119, 719)( 120, 996)
( 121, 431)( 122, 401)( 123, 939)( 124,1168)( 125, 958)( 126, 995)
( 127, 611)( 130,1220)( 131, 178)( 132, 785)( 133, 517)( 135,1511)
( 136, 551)( 137,1201)( 139,1139)( 140,1699)( 141,2064)( 142,1805)
( 143, 963)( 144, 425)( 145,1760)( 146, 696)( 147, 240)( 148,1557)
( 149, 637)( 150, 476)( 151, 953)( 152, 708)( 153,1340)( 154, 440)
( 155, 550)( 156,1855)( 157,1283)( 158, 704)( 159,1522)( 160, 188)
( 161,1109)( 163,1681)( 164,1150)( 165,2021)( 167,1077)( 168,1408)
( 169, 674)( 170,1121)( 171, 340)( 172, 339)( 173, 846)( 175, 817)
( 176,1162)( 177, 317)( 179,1303)( 181,1650)( 182,1477)( 183, 508)
( 184,1043)( 185,1605)( 186,2022)( 189, 462)( 190, 436)( 191, 700)
( 192,1106)( 193, 752)( 194, 291)( 195,1075)( 196, 825)( 197,2043)
( 198, 677)( 199,2060)( 200, 687)( 201, 571)( 202,2141)( 203,1376)
( 204,2089)( 205, 400)( 206, 564)( 207, 769)( 208, 652)( 209,1994)
( 210,1223)( 211,1316)( 212, 555)( 213,1289)( 214,1004)( 215, 919)
( 216, 918)( 217, 344)( 218,1085)( 219,1302)( 220,1616)( 221, 812)
( 222, 363)( 223, 903)( 224, 860)( 225, 433)( 226, 643)( 227, 492)
( 228, 527)( 229, 503)( 230,1645)( 231,1320)( 232, 678)( 233,1280)
( 234,1897)( 235, 962)( 236, 365)( 237,1959)( 238, 753)( 239,1396)
( 241, 628)( 242, 256)( 243,1903)( 245, 834)( 246,1829)( 248, 324)
( 249,1773)( 250,1531)( 251, 518)( 253,1581)( 254, 269)( 257,1932)
( 258, 809)( 259, 854)( 260,2090)( 261,2048)( 262, 862)( 263, 726)
( 264,1825)( 265,1342)( 266,1290)( 267,1074)( 268,1159)( 270,1325)
( 271,1565)( 272,1020)( 273,1729)( 274, 711)( 275, 968)( 276, 681)
( 277,1876)( 278, 640)( 279,1299)( 280, 714)( 281,1476)( 282,1953)
( 283, 419)( 284,1444)( 285,1251)( 286, 379)( 287, 954)( 288, 563)
( 290,1483)( 292,1105)( 294,1817)( 296, 863)( 297, 690)( 298, 382)
( 300,1587)( 301, 383)( 302, 593)( 303,1593)( 304, 822)( 305, 495)
( 306,2182)( 307,2173)( 308,1279)( 309, 724)( 310,1992)( 311, 331)
( 312,1693)( 313, 319)( 314, 455)( 315,1936)( 316,1673)( 318, 739)
( 320,1056)( 322,1072)( 323,1231)( 325, 820)( 326,1853)( 327, 815)
( 330,1353)( 332, 686)( 333, 887)( 335, 592)( 336,2143)( 337,2033)
( 341, 859)( 342,1398)( 343,1420)( 345,1664)( 346,1981)( 347, 990)
( 348, 929)( 349,1014)( 350,2152)( 351,1070)( 352,1687)( 353,1089)
( 354, 562)( 355,1539)( 356, 787)( 357,1630)( 358,1081)( 359,1488)
( 360,1426)( 361,1031)( 362,1156)( 366,1123)( 368,1154)( 369,1478)
( 371,1841)( 372, 446)( 373,2079)( 374,1612)( 375,1514)( 376,1714)
( 377,1416)( 378, 404)( 380,1265)( 381,1639)( 384, 578)( 385,1111)
( 386,1576)( 387,1147)( 388, 967)( 389,2031)( 390,1717)( 392,1238)
( 393,1706)( 394,1746)( 395,1703)( 396,1512)( 397,2087)( 398,1819)
( 399,1435)( 402,1222)( 405, 838)( 406, 997)( 407,1911)( 408,1243)
( 409,1503)( 410,1319)( 411,1990)( 412, 496)( 413,1856)( 414,1091)
( 415,1310)( 417,1484)( 418, 799)( 420, 689)( 421,2191)( 422,1221)
( 423,2011)( 424,1906)( 426,1354)( 427, 801)( 429,1268)( 430,1724)
( 432, 920)( 434, 976)( 435, 709)( 437, 730)( 438,2002)( 439,1879)
( 441, 478)( 442,1188)( 445,1912)( 447,1000)( 448,1579)( 449,1816)
( 450,1267)( 452, 549)( 453, 892)( 454,1771)( 456, 858)( 458,2109)
( 459,1050)( 460,1138)( 461,1857)( 463,1957)( 464,1184)( 465,2063)
( 466, 853)( 467,2124)( 468,1131)( 470, 847)( 471,2165)( 472,1248)
( 473, 613)( 474,1880)( 475,1257)( 479, 965)( 480, 780)( 481,1429)
( 482,1002)( 483,1439)( 484,1187)( 485,1482)( 486,1920)( 487,1362)
( 488,2193)( 490,1206)( 491,1258)( 493,1788)( 494, 842)( 497,2179)
( 498, 843)( 499,1873)( 500,1787)( 501,1756)( 502,1029)( 504,1247)
( 505,1260)( 506, 889)( 507,1401)( 509,1538)( 510,2099)( 511, 607)
( 512,1244)( 513, 610)( 514, 833)( 515,1640)( 516,1732)( 519,1744)
( 521,1962)( 522,1838)( 523,1218)( 524,2122)( 525,1068)( 526, 641)
( 528,1407)( 529,1025)( 530,2018)( 531, 872)( 532, 684)( 533,1037)
( 534,1454)( 535, 729)( 536,1694)( 537, 697)( 538,1058)( 539, 910)
( 540, 660)( 541,1335)( 542,2014)( 543,1271)( 544,1240)( 545,1780)
( 546, 989)( 547, 606)( 548,1214)( 552,1291)( 553,1359)( 556,1712)
( 557,1614)( 558, 791)( 559,2010)( 560,1063)( 561,1767)( 565,1518)
( 566,1999)( 567,2127)( 568, 770)( 569,2108)( 570,1277)( 573,1179)
( 574, 957)( 575, 821)( 576,1107)( 577,1409)( 580,1225)( 581,2098)
( 582, 899)( 583,2045)( 584,1955)( 585,1371)( 586,1642)( 587,1100)
( 588,1458)( 589, 904)( 590,1904)( 591,1859)( 594,2054)( 595,1577)
( 596,1007)( 597,2017)( 598, 668)( 599,1989)( 600,1893)( 602,1961)
( 603,1980)( 604,1102)( 605,1991)( 608,2028)( 609,1623)( 612,2024)
( 614,1122)( 616,1161)( 617,1824)( 618,1448)( 619,1447)( 620,1415)
( 621,1381)( 622,1030)( 623,1296)( 624, 890)( 625,1314)( 626,1510)
( 627,1742)( 629, 839)( 630,2134)( 631,1808)( 632,2121)( 633,1559)
( 634, 635)( 636,1317)( 638, 943)( 639,1388)( 642,1823)( 644,1526)
( 645,1341)( 646,1507)( 647,1766)( 648,1132)( 649,2137)( 650,1638)
( 651, 901)( 653, 754)( 654,2125)( 655,1093)( 656,1153)( 657, 715)
( 658,1954)( 659,2136)( 661,1001)( 662, 950)( 663,1976)( 664,1453)
( 665,1636)( 666,1281)( 667,1446)( 669,1573)( 670,1599)( 671,1015)
( 672,2038)( 673,1423)( 675,1935)( 679, 988)( 680,1513)( 682,1295)
( 683,1713)( 685,2189)( 688,1515)( 691,1430)( 692,1591)( 693,1489)
( 694,2159)( 695,1033)( 698, 837)( 699,1166)( 702, 764)( 703,1044)
( 705, 733)( 706,2197)( 707, 823)( 710,1143)( 712,1865)( 713,1996)
( 716,1249)( 717, 933)( 718,1224)( 720,1235)( 721,1627)( 722,1974)
( 723,1811)( 725,1163)( 727,2102)( 728,1652)( 731,1431)( 734,2015)
( 735,2171)( 736,1544)( 737, 956)( 738,1572)( 740,1372)( 741,1781)
( 742,1594)( 743,1566)( 744, 959)( 745,1119)( 746,1198)( 747,1252)
( 748, 960)( 749,1101)( 750,1546)( 751,1868)( 756,2006)( 757,1613)
( 758, 983)( 759, 926)( 760,1549)( 761,1421)( 762,1916)( 763, 937)
( 765,2013)( 766,1795)( 767,2036)( 768,1969)( 771, 900)( 772,1603)
( 773,1509)( 774,1535)( 775,1696)( 776,1682)( 777, 898)( 778,1368)
( 779,1228)( 781,1641)( 782,1908)( 783,2150)( 784,1363)( 786,2114)
( 788, 797)( 789,1809)( 790,1493)( 792,1777)( 794,1028)( 795,1846)
( 796,1768)( 798,1928)( 800,1934)( 802,1428)( 803,2140)( 804,1708)
( 805,1331)( 806,1747)( 807,1384)( 808,1217)( 810,1294)( 811,1801)
( 813,1888)( 814, 828)( 816,1424)( 818, 986)( 819,1233)( 824, 826)
( 827,1584)( 829,2077)( 830, 916)( 831,1481)( 832,1894)( 835,1322)
( 836,1427)( 840,1775)( 841,1843)( 845,1487)( 848,1117)( 849,1782)
( 850,1803)( 851,1618)( 852,1877)( 855,1172)( 856,1634)( 857,1635)
( 861,1069)( 864,1528)( 865,1367)( 866,1492)( 867,1049)( 868,1764)
( 869,1011)( 870,1016)( 871,2047)( 873,1181)( 874,2148)( 875,1983)
( 876,1364)( 877, 961)( 878,2104)( 879,1274)( 880,1140)( 881,1193)
( 882,2147)( 883,2100)( 884, 975)( 885,1952)( 886,1834)( 888,1378)
( 891,1508)( 893,1276)( 894,1474)( 895,1346)( 896,1151)( 897,2153)
( 902,1759)( 905,1405)( 906,1550)( 908,1382)( 909,1695)( 911,1082)
( 913,1095)( 914,1923)( 915,1459)( 917,1288)( 921,1845)( 922,1648)
( 923,1743)( 924,1831)( 925,1739)( 927,2088)( 928,1849)( 930,1324)
( 931,1940)( 932,2174)( 935,2029)( 936,1256)( 940,2096)( 941,1032)
( 942,1702)( 944,1647)( 945,1679)( 946,1344)( 947,2080)( 948,1734)
( 949,2162)( 951,1987)( 952,1456)( 964,2185)( 966,1437)( 969,2188)
( 970,1554)( 971,2027)( 972, 993)( 973,2091)( 974,1506)( 977,1356)
( 978,1160)( 979,1886)( 980,1776)( 981,1337)( 982,2144)( 985,1602)
( 987,2111)( 991,2081)( 992,2110)( 994,1704)( 998,1311)( 999,1665)
(1003,1700)(1005,1675)(1006,1862)(1008,1727)(1009,1941)(1012,1349)
(1013,1571)(1017,1914)(1018,2062)(1019,1978)(1021,2187)(1022,1653)
(1023,1273)(1024,1939)(1026,1793)(1027,1733)(1034,1355)(1035,1874)
(1036,1521)(1038,1919)(1039,1094)(1040,1590)(1041,1672)(1042,1814)
(1045,1491)(1046,1564)(1047,1619)(1048,1666)(1051,1377)(1052,1705)
(1053,1907)(1054,1180)(1055,1133)(1057,1925)(1059,1301)(1060,1711)
(1061,1800)(1062,1678)(1064,1216)(1065,1232)(1066,1942)(1067,2001)
(1071,1626)(1073,2183)(1076,2177)(1078,1084)(1079,1110)(1080,1369)
(1083,1360)(1086,1229)(1087,1737)(1088,1622)(1090,1332)(1092,2052)
(1096,1241)(1097,1960)(1098,1719)(1099,1418)(1103,1141)(1104,2020)
(1108,1791)(1112,1350)(1113,2132)(1115,1551)(1116,1725)(1118,1387)
(1120,1326)(1124,1552)(1125,1631)(1126,1651)(1127,1608)(1128,1710)
(1130,1931)(1134,1164)(1135,1615)(1136,2051)(1137,1740)(1142,1461)
(1144,2049)(1145,1471)(1146,1174)(1148,2019)(1149,1585)(1152,2039)
(1155,1287)(1157,1561)(1158,1300)(1165,1628)(1167,2128)(1169,1830)
(1170,2138)(1171,1463)(1173,2126)(1175,1397)(1177,1199)(1178,1950)
(1182,1537)(1183,1562)(1186,1854)(1190,1720)(1191,1348)(1192,1833)
(1194,1196)(1197,1993)(1200,1338)(1202,1887)(1205,1852)(1207,1400)
(1208,1889)(1210,2142)(1211,1411)(1212,2184)(1213,1527)(1215,1621)
(1219,1473)(1226,2012)(1227,1347)(1230,1393)(1234,1822)(1237,1259)
(1239,2130)(1242,1649)(1245,1772)(1246,1871)(1253,1927)(1254,1870)
(1255,1596)(1262,1588)(1264,1624)(1266,1460)(1269,1716)(1270,1688)
(1272,1345)(1275,1972)(1282,1536)(1284,1568)(1285,1821)(1286,2004)
(1292,1670)(1293,1504)(1297,1633)(1304,1842)(1305,1327)(1307,1847)
(1308,1365)(1309,2151)(1312,1394)(1313,1806)(1315,2046)(1318,1799)
(1321,1373)(1323,2170)(1328,2198)(1329,1663)(1330,2161)(1334,2145)
(1336,2066)(1339,1718)(1343,1495)(1351,2123)(1352,1433)(1357,1902)
(1361,1502)(1366,1600)(1370,2059)(1374,1517)(1375,1499)(1379,2120)
(1380,1451)(1385,1835)(1386,1524)(1389,1570)(1390,2082)(1391,2176)
(1392,1442)(1395,1988)(1402,1697)(1403,1826)(1404,2195)(1406,1913)
(1410,1465)(1412,2112)(1413,1786)(1417,2032)(1422,2194)(1425,2035)
(1432,1728)(1434,1965)(1436,2076)(1438,1761)(1440,2007)(1441,1583)
(1445,1516)(1449,1580)(1450,1689)(1452,2118)(1457,1832)(1462,1598)
(1466,1966)(1467,1875)(1468,1505)(1469,1486)(1470,1558)(1472,2026)
(1475,2068)(1479,1754)(1480,2154)(1490,2093)(1494,2175)(1496,1723)
(1497,1984)(1498,2075)(1500,1963)(1501,1971)(1520,2181)(1525,1691)
(1530,1656)(1532,1753)(1533,1860)(1534,1553)(1540,1662)(1541,2178)
(1542,1620)(1543,1827)(1545,1881)(1548,1968)(1556,1690)(1560,1655)
(1563,2061)(1567,1967)(1569,1601)(1575,1929)(1578,1884)(1582,2092)
(1586,1684)(1589,2097)(1592,1848)(1595,2158)(1597,1890)(1604,1970)
(1606,2034)(1609,1680)(1611,1997)(1617,1944)(1625,2131)(1632,2146)
(1637,1807)(1643,1722)(1644,2156)(1654,1863)(1657,1995)(1658,1752)
(1660,1844)(1661,2086)(1667,1973)(1668,2149)(1669,1802)(1671,1946)
(1674,1676)(1685,1709)(1686,1924)(1692,1785)(1698,1964)(1701,1763)
(1707,1977)(1715,1745)(1721,1779)(1726,1778)(1731,1951)(1735,2037)
(1736,1878)(1738,1937)(1741,1794)(1749,1789)(1750,1828)(1751,1896)
(1757,2016)(1758,1797)(1765,2030)(1769,1945)(1770,2065)(1783,2166)
(1784,1910)(1792,2055)(1796,2139)(1798,1891)(1804,1947)(1810,1958)
(1813,2000)(1815,2008)(1818,1926)(1820,2053)(1836,2070)(1837,1915)
(1839,1975)(1840,1998)(1850,2056)(1851,2117)(1861,2160)(1864,1883)
(1866,2009)(1867,2163)(1882,1985)(1885,1892)(1895,1905)(1898,2105)
(1899,2078)(1900,2069)(1901,2186)(1909,2071)(1917,2107)(1918,2196)
(1930,2042)(1943,2041)(1948,2003)(1949,2005)(1956,2050)(1979,2044)
(2023,2135)(2025,2084)(2057,2192)(2067,2103)(2074,2190)(2083,2155)
(2094,2164)(2095,2113)(2101,2116)(2115,2133)(2119,2157)(2172,2180);