from functools import cache #import cProfile s = {1: 0, 3: 2, 5: 0, 7: 2, 9: 8, 11: 10, 13: 8, 15: 10, 17: 0, 19: 2, 21: 0, 23: 2, 25: 8, 27: 10, 29: 8, 31: 10, 33: 32, 35: 34, 37: 32, 39: 34, 41: 40, 43: 42, 45: 40, 47: 42, 49: 32, 51: 34, 53: 32, 55: 34, 57: 40, 59: 42, 61: 40, 63: 42, 65: 0, 67: 2, 69: 0, 71: 2, 73: 8, 75: 10, 77: 8, 79: 10, 81: 0, 83: 2, 85: 0, 87: 2, 89: 8, 91: 10, 93: 8, 95: 10, 97: 32, 99: 34, 101: 32, 103: 34, 105: 40, 107: 42, 109: 40, 111: 42, 113: 32, 115: 34, 117: 32, 119: 34, 121: 40, 123: 42, 125: 40, 127: 42, 129: 128, 131: 130, 133: 128, 135: 130, 137: 136, 139: 138, 141: 136, 143: 138, 145: 128, 147: 130, 149: 128, 151: 130, 153: 136, 155: 138, 157: 136, 159: 138, 161: 160, 163: 162, 165: 160, 167: 162, 169: 168, 171: 170, 173: 168, 175: 170, 177: 160, 179: 162, 181: 160, 183: 162, 185: 168, 187: 170, 189: 168, 191: 170, 193: 128, 195: 130, 197: 128, 199: 130, 201: 136, 203: 138, 205: 136, 207: 138, 209: 128, 211: 130, 213: 128, 215: 130, 217: 136, 219: 138, 221: 136, 223: 138, 225: 160, 227: 162, 229: 160, 231: 162, 233: 168, 235: 170, 237: 168, 239: 170, 241: 160, 243: 162, 245: 160, 247: 162, 249: 168, 251: 170, 253: 168, 255: 170, 257: 0, 259: 2, 261: 0, 263: 2, 265: 8, 267: 10, 269: 8, 271: 10, 273: 0, 275: 2, 277: 0, 279: 2, 281: 8, 283: 10, 285: 8, 287: 10, 289: 32, 291: 34, 293: 32, 295: 34, 297: 40, 299: 42, 301: 40, 303: 42, 305: 32, 307: 34, 309: 32, 311: 34, 313: 40, 315: 42, 317: 40, 319: 42, 321: 0, 323: 2, 325: 0, 327: 2, 329: 8, 331: 10, 333: 8, 335: 10, 337: 0, 339: 2, 341: 0, 343: 2, 345: 8, 347: 10, 349: 8, 351: 10, 353: 32, 355: 34, 357: 32, 359: 34, 361: 40, 363: 42, 365: 40, 367: 42, 369: 32, 371: 34, 373: 32, 375: 34, 377: 40, 379: 42, 381: 40, 383: 42, 385: 128, 387: 130, 389: 128, 391: 130, 393: 136, 395: 138, 397: 136, 399: 138, 401: 128, 403: 130, 405: 128, 407: 130, 409: 136, 411: 138, 413: 136, 415: 138, 417: 160, 419: 162, 421: 160, 423: 162, 425: 168, 427: 170, 429: 168, 431: 170, 433: 160, 435: 162, 437: 160, 439: 162, 441: 168, 443: 170, 445: 168, 447: 170, 449: 128, 451: 130, 453: 128, 455: 130, 457: 136, 459: 138, 461: 136, 463: 138, 465: 128, 467: 130, 469: 128, 471: 130, 473: 136, 475: 138, 477: 136, 479: 138, 481: 160, 483: 162, 485: 160, 487: 162, 489: 168, 491: 170, 493: 168, 495: 170, 497: 160, 499: 162, 501: 160, 503: 162, 505: 168, 507: 170, 509: 168, 511: 170, 513: 512, 515: 514, 517: 512, 519: 514, 521: 520, 523: 522, 525: 520, 527: 522, 529: 512, 531: 514, 533: 512, 535: 514, 537: 520, 539: 522, 541: 520, 543: 522, 545: 544, 547: 546, 549: 544, 551: 546, 553: 552, 555: 554, 557: 552, 559: 554, 561: 544, 563: 546, 565: 544, 567: 546, 569: 552, 571: 554, 573: 552, 575: 554, 577: 512, 579: 514, 581: 512, 583: 514, 585: 520, 587: 522, 589: 520, 591: 522, 593: 512, 595: 514, 597: 512, 599: 514, 601: 520, 603: 522, 605: 520, 607: 522, 609: 544, 611: 546, 613: 544, 615: 546, 617: 552, 619: 554, 621: 552, 623: 554, 625: 544, 627: 546, 629: 544, 631: 546, 633: 552, 635: 554, 637: 552, 639: 554, 641: 640, 643: 642, 645: 640, 647: 642, 649: 648, 651: 650, 653: 648, 655: 650, 657: 640, 659: 642, 661: 640, 663: 642, 665: 648, 667: 650, 669: 648, 671: 650, 673: 672, 675: 674, 677: 672, 679: 674, 681: 680, 683: 682, 685: 680, 687: 682, 689: 672, 691: 674, 693: 672, 695: 674, 697: 680, 699: 682, 701: 680, 703: 682, 705: 640, 707: 642, 709: 640, 711: 642, 713: 648, 715: 650, 717: 648, 719: 650, 721: 640, 723: 642, 725: 640, 727: 642, 729: 648, 731: 650, 733: 648, 735: 650, 737: 672, 739: 674, 741: 672, 743: 674, 745: 680, 747: 682, 749: 680, 751: 682, 753: 672, 755: 674, 757: 672, 759: 674, 761: 680, 763: 682, 765: 680, 767: 682, 769: 512, 771: 514, 773: 512, 775: 514, 777: 520, 779: 522, 781: 520, 783: 522, 785: 512, 787: 514, 789: 512, 791: 514, 793: 520, 795: 522, 797: 520, 799: 522, 801: 544, 803: 546, 805: 544, 807: 546, 809: 552, 811: 554, 813: 552, 815: 554, 817: 544, 819: 546, 821: 544, 823: 546, 825: 552, 827: 554, 829: 552, 831: 554, 833: 512, 835: 514, 837: 512, 839: 514, 841: 520, 843: 522, 845: 520, 847: 522, 849: 512, 851: 514, 853: 512, 855: 514, 857: 520, 859: 522, 861: 520, 863: 522, 865: 544, 867: 546, 869: 544, 871: 546, 873: 552, 875: 554, 877: 552, 879: 554, 881: 544, 883: 546, 885: 544, 887: 546, 889: 552, 891: 554, 893: 552, 895: 554, 897: 640, 899: 642, 901: 640, 903: 642, 905: 648, 907: 650, 909: 648, 911: 650, 913: 640, 915: 642, 917: 640, 919: 642, 921: 648, 923: 650, 925: 648, 927: 650, 929: 672, 931: 674, 933: 672, 935: 674, 937: 680, 939: 682, 941: 680, 943: 682, 945: 672, 947: 674, 949: 672, 951: 674, 953: 680, 955: 682, 957: 680, 959: 682, 961: 640, 963: 642, 965: 640, 967: 642, 969: 648, 971: 650, 973: 648, 975: 650, 977: 640, 979: 642, 981: 640, 983: 642, 985: 648, 987: 650, 989: 648, 991: 650, 993: 672, 995: 674, 997: 672, 999: 674, 1001: 680, 1003: 682, 1005: 680, 1007: 682, 1009: 672, 1011: 674, 1013: 672, 1015: 674, 1017: 680, 1019: 682, 1021: 680, 1023: 682, 1025: 0, 1027: 2, 1029: 0, 1031: 2, 1033: 8, 1035: 10, 1037: 8, 1039: 10, 1041: 0, 1043: 2, 1045: 0, 1047: 2, 1049: 8, 1051: 10, 1053: 8, 1055: 10, 1057: 32, 1059: 34, 1061: 32, 1063: 34, 1065: 40, 1067: 42, 1069: 40, 1071: 42, 1073: 32, 1075: 34, 1077: 32, 1079: 34, 1081: 40, 1083: 42, 1085: 40, 1087: 42, 1089: 0, 1091: 2, 1093: 0, 1095: 2, 1097: 8, 1099: 10, 1101: 8, 1103: 10, 1105: 0, 1107: 2, 1109: 0, 1111: 2, 1113: 8, 1115: 10, 1117: 8, 1119: 10, 1121: 32, 1123: 34, 1125: 32, 1127: 34, 1129: 40, 1131: 42, 1133: 40, 1135: 42, 1137: 32, 1139: 34, 1141: 32, 1143: 34, 1145: 40, 1147: 42, 1149: 40, 1151: 42, 1153: 128, 1155: 130, 1157: 128, 1159: 130, 1161: 136, 1163: 138, 1165: 136, 1167: 138, 1169: 128, 1171: 130, 1173: 128, 1175: 130, 1177: 136, 1179: 138, 1181: 136, 1183: 138, 1185: 160, 1187: 162, 1189: 160, 1191: 162, 1193: 168, 1195: 170, 1197: 168, 1199: 170, 1201: 160, 1203: 162, 1205: 160, 1207: 162, 1209: 168, 1211: 170, 1213: 168, 1215: 170, 1217: 128, 1219: 130, 1221: 128, 1223: 130, 1225: 136, 1227: 138, 1229: 136, 1231: 138, 1233: 128, 1235: 130, 1237: 128, 1239: 130, 1241: 136, 1243: 138, 1245: 136, 1247: 138, 1249: 160, 1251: 162, 1253: 160, 1255: 162, 1257: 168, 1259: 170, 1261: 168, 1263: 170, 1265: 160, 1267: 162, 1269: 160, 1271: 162, 1273: 168, 1275: 170, 1277: 168, 1279: 170, 1281: 0, 1283: 2, 1285: 0, 1287: 2, 1289: 8, 1291: 10, 1293: 8, 1295: 10, 1297: 0, 1299: 2, 1301: 0, 1303: 2, 1305: 8, 1307: 10, 1309: 8, 1311: 10, 1313: 32, 1315: 34, 1317: 32, 1319: 34, 1321: 40, 1323: 42, 1325: 40, 1327: 42, 1329: 32, 1331: 34, 1333: 32, 1335: 34, 1337: 40, 1339: 42, 1341: 40, 1343: 42, 1345: 0, 1347: 2, 1349: 0, 1351: 2, 1353: 8, 1355: 10, 1357: 8, 1359: 10, 1361: 0, 1363: 2, 1365: 0, 1367: 2, 1369: 8, 1371: 10, 1373: 8, 1375: 10, 1377: 32, 1379: 34, 1381: 32, 1383: 34, 1385: 40, 1387: 42, 1389: 40, 1391: 42, 1393: 32, 1395: 34, 1397: 32, 1399: 34, 1401: 40, 1403: 42, 1405: 40, 1407: 42, 1409: 128, 1411: 130, 1413: 128, 1415: 130, 1417: 136, 1419: 138, 1421: 136, 1423: 138, 1425: 128, 1427: 130, 1429: 128, 1431: 130, 1433: 136, 1435: 138, 1437: 136, 1439: 138, 1441: 160, 1443: 162, 1445: 160, 1447: 162, 1449: 168, 1451: 170, 1453: 168, 1455: 170, 1457: 160, 1459: 162, 1461: 160, 1463: 162, 1465: 168, 1467: 170, 1469: 168, 1471: 170, 1473: 128, 1475: 130, 1477: 128, 1479: 130, 1481: 136, 1483: 138, 1485: 136, 1487: 138, 1489: 128, 1491: 130, 1493: 128, 1495: 130, 1497: 136, 1499: 138, 1501: 136, 1503: 138, 1505: 160, 1507: 162, 1509: 160, 1511: 162, 1513: 168, 1515: 170, 1517: 168, 1519: 170, 1521: 160, 1523: 162, 1525: 160, 1527: 162, 1529: 168, 1531: 170, 1533: 168, 1535: 170, 1537: 512, 1539: 514, 1541: 512, 1543: 514, 1545: 520, 1547: 522, 1549: 520, 1551: 522, 1553: 512, 1555: 514, 1557: 512, 1559: 514, 1561: 520, 1563: 522, 1565: 520, 1567: 522, 1569: 544, 1571: 546, 1573: 544, 1575: 546, 1577: 552, 1579: 554, 1581: 552, 1583: 554, 1585: 544, 1587: 546, 1589: 544, 1591: 546, 1593: 552, 1595: 554, 1597: 552, 1599: 554, 1601: 512, 1603: 514, 1605: 512, 1607: 514, 1609: 520, 1611: 522, 1613: 520, 1615: 522, 1617: 512, 1619: 514, 1621: 512, 1623: 514, 1625: 520, 1627: 522, 1629: 520, 1631: 522, 1633: 544, 1635: 546, 1637: 544, 1639: 546, 1641: 552, 1643: 554, 1645: 552, 1647: 554, 1649: 544, 1651: 546, 1653: 544, 1655: 546, 1657: 552, 1659: 554, 1661: 552, 1663: 554, 1665: 640, 1667: 642, 1669: 640, 1671: 642, 1673: 648, 1675: 650, 1677: 648, 1679: 650, 1681: 640, 1683: 642, 1685: 640, 1687: 642, 1689: 648, 1691: 650, 1693: 648, 1695: 650, 1697: 672, 1699: 674, 1701: 672, 1703: 674, 1705: 680, 1707: 682, 1709: 680, 1711: 682, 1713: 672, 1715: 674, 1717: 672, 1719: 674, 1721: 680, 1723: 682, 1725: 680, 1727: 682, 1729: 640, 1731: 642, 1733: 640, 1735: 642, 1737: 648, 1739: 650, 1741: 648, 1743: 650, 1745: 640, 1747: 642, 1749: 640, 1751: 642, 1753: 648, 1755: 650, 1757: 648, 1759: 650, 1761: 672, 1763: 674, 1765: 672, 1767: 674, 1769: 680, 1771: 682, 1773: 680, 1775: 682, 1777: 672, 1779: 674, 1781: 672, 1783: 674, 1785: 680, 1787: 682, 1789: 680, 1791: 682, 1793: 512, 1795: 514, 1797: 512, 1799: 514, 1801: 520, 1803: 522, 1805: 520, 1807: 522, 1809: 512, 1811: 514, 1813: 512, 1815: 514, 1817: 520, 1819: 522, 1821: 520, 1823: 522, 1825: 544, 1827: 546, 1829: 544, 1831: 546, 1833: 552, 1835: 554, 1837: 552, 1839: 554, 1841: 544, 1843: 546, 1845: 544, 1847: 546, 1849: 552, 1851: 554, 1853: 552, 1855: 554, 1857: 512, 1859: 514, 1861: 512, 1863: 514, 1865: 520, 1867: 522, 1869: 520, 1871: 522, 1873: 512, 1875: 514, 1877: 512, 1879: 514, 1881: 520, 1883: 522, 1885: 520, 1887: 522, 1889: 544, 1891: 546, 1893: 544, 1895: 546, 1897: 552, 1899: 554, 1901: 552, 1903: 554, 1905: 544, 1907: 546, 1909: 544, 1911: 546, 1913: 552, 1915: 554, 1917: 552, 1919: 554, 1921: 640, 1923: 642, 1925: 640, 1927: 642, 1929: 648, 1931: 650, 1933: 648, 1935: 650, 1937: 640, 1939: 642, 1941: 640, 1943: 642, 1945: 648, 1947: 650, 1949: 648, 1951: 650, 1953: 672, 1955: 674, 1957: 672, 1959: 674, 1961: 680, 1963: 682, 1965: 680, 1967: 682, 1969: 672, 1971: 674, 1973: 672, 1975: 674, 1977: 680, 1979: 682, 1981: 680, 1983: 682, 1985: 640, 1987: 642, 1989: 640, 1991: 642, 1993: 648, 1995: 650, 1997: 648, 1999: 650, } @cache def calc(n): if n %2 == 0: n-=1 if n in s: return s[n] #print(n) maxp = 0 while 2 ** maxp < n: maxp += 1 maxp -= 1 #print(maxp) if maxp % 2 == 0: return calc(n - 2 ** maxp) return calc(n - 2 ** maxp) + 2 ** maxp #pr = cProfile.Profile() #pr.enable() with open("a.txt") as fi: with open("biscuits.out", "w") as f: fl = fi.readlines() t = int(fl[0]) for i in range(1, t + 1): n = int(fl[i]) f.write(str(calc(n) + 1) + "\n") #pr.disable() #import io, pstats #from pstats import SortKey #s = io.StringIO() #sortby = SortKey.CUMULATIVE #ps = pstats.Stats(pr, stream=s).sort_stats(sortby) #ps.print_stats() #print(s.getvalue())