def _next(idx, xs):
    x, y = divmod(idx, 3)
    b = [list(xs[:3]), list(xs[3: 6]), list(xs[6:])]
    for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        u, v = x + dx, y + dy
        if 0 <= u < 3 and 0 <= v < 3:
            b[u][v] = "1" if b[u][v] == "0" else "0"
    b[x][y] = "1" if b[x][y] == "0" else "0"
    return ''.join(b[0]) +''.join(b[1])+''.join(b[2])

def dfs(s):
    q = [(s, "0" * 9)]
    visited = set(s)
    while q:
        e, p = q.pop(0)
        if e == '1' * 9:
            return p
        for idx in range(9):            
            ne = _next(idx, e)
            if not ne in visited:
                visited.add(ne)
                q.append((ne, p[:idx]+"1"+p[idx +1:]))

                
s = []
d = {'000000000': '101010101', '000000001': '110110000', '000000010': '010000101', '000000011': '001100000', '000000100': '011011000', '000000101': '000111101', '000000110': '100001000', '000000111': '111101101', '000001000': '001100001', '000001001': '010000100', '000001010': '110110001', '000001011': '101010100', '000001100': '111101100', '000001101': '100001001', '000001110': '000111100', '000001111': '011011001', '000010000': '111101111', '000010001': '100001010', '000010010': '000111111', '000010011': '011011010', '000010100': '001100010', '000010101': '010000111', '000010110': '110110010', '000010111': '101010111', '000011000': '011011011', '000011001': '000111110', '000011010': '100001011', '000011011': '111101110', '000011100': '101010110', '000011101': '110110011', '000011110': '010000110', '000011111': '001100011', '000100000': '100001100', '000100001': '111101001', '000100010': '011011100', '000100011': '000111001', '000100100': '010000001', '000100101': '001100100', '000100110': '101010001', '000100111': '110110100', '000101000': '000111000', '000101001': '011011101', '000101010': '111101000', '000101011': '100001101', '000101100': '110110101', '000101101': '101010000', '000101110': '001100101', '000101111': '010000000', '000110000': '110110110', '000110001': '101010011', '000110010': '001100110', '000110011': '010000011', '000110100': '000111011', '000110101': '011011110', '000110110': '111101011', '000110111': '100001110', '000111000': '010000010', '000111001': '001100111', '000111010': '101010010', '000111011': '110110111', '000111100': '100001111', '000111101': '111101010', '000111110': '011011111', '000111111': '000111010', '001000000': '000110110', '001000001': '011010011', '001000010': '111100110', '001000011': '100000011', '001000100': '110111011', '001000101': '101011110', '001000110': '001101011', '001000111': '010001110', '001001000': '100000010', '001001001': '111100111', '001001010': '011010010', '001001011': '000110111', '001001100': '010001111', '001001101': '001101010', '001001110': '101011111', '001001111': '110111010', '001010000': '010001100', '001010001': '001101001', '001010010': '101011100', '001010011': '110111001', '001010100': '100000001', '001010101': '111100100', '001010110': '011010001', '001010111': '000110100', '001011000': '110111000', '001011001': '101011101', '001011010': '001101000', '001011011': '010001101', '001011100': '000110101', '001011101': '011010000', '001011110': '111100101', '001011111': '100000000', '001100000': '001101111', '001100001': '010001010', '001100010': '110111111', '001100011': '101011010', '001100100': '111100010', '001100101': '100000111', '001100110': '000110010', '001100111': '011010111', '001101000': '101011011', '001101001': '110111110', '001101010': '010001011', '001101011': '001101110', '001101100': '011010110', '001101101': '000110011', '001101110': '100000110', '001101111': '111100011', '001110000': '011010101', '001110001': '000110000', '001110010': '100000101', '001110011': '111100000', '001110100': '101011000', '001110101': '110111101', '001110110': '010001000', '001110111': '001101101', '001111000': '111100001', '001111001': '100000100', '001111010': '000110001', '001111011': '011010100', '001111100': '001101100', '001111101': '010001001', '001111110': '110111100', '001111111': '101011001', '010000000': '101000010', '010000001': '110100111', '010000010': '010010010', '010000011': '001110111', '010000100': '011001111', '010000101': '000101010', '010000110': '100011111', '010000111': '111111010', '010001000': '001110110', '010001001': '010010011', '010001010': '110100110', '010001011': '101000011', '010001100': '111111011', '010001101': '100011110', '010001110': '000101011', '010001111': '011001110', '010010000': '111111000', '010010001': '100011101', '010010010': '000101000', '010010011': '011001101', '010010100': '001110101', '010010101': '010010000', '010010110': '110100101', '010010111': '101000000', '010011000': '011001100', '010011001': '000101001', '010011010': '100011100', '010011011': '111111001', '010011100': '101000001', '010011101': '110100100', '010011110': '010010001', '010011111': '001110100', '010100000': '100011011', '010100001': '111111110', '010100010': '011001011', '010100011': '000101110', '010100100': '010010110', '010100101': '001110011', '010100110': '101000110', '010100111': '110100011', '010101000': '000101111', '010101001': '011001010', '010101010': '111111111', '010101011': '100011010', '010101100': '110100010', '010101101': '101000111', '010101110': '001110010', '010101111': '010010111', '010110000': '110100001', '010110001': '101000100', '010110010': '001110001', '010110011': '010010100', '010110100': '000101100', '010110101': '011001001', '010110110': '111111100', '010110111': '100011001', '010111000': '010010101', '010111001': '001110000', '010111010': '101000101', '010111011': '110100000', '010111100': '100011000', '010111101': '111111101', '010111110': '011001000', '010111111': '000101101', '011000000': '000100001', '011000001': '011000100', '011000010': '111110001', '011000011': '100010100', '011000100': '110101100', '011000101': '101001001', '011000110': '001111100', '011000111': '010011001', '011001000': '100010101', '011001001': '111110000', '011001010': '011000101', '011001011': '000100000', '011001100': '010011000', '011001101': '001111101', '011001110': '101001000', '011001111': '110101101', '011010000': '010011011', '011010001': '001111110', '011010010': '101001011', '011010011': '110101110', '011010100': '100010110', '011010101': '111110011', '011010110': '011000110', '011010111': '000100011', '011011000': '110101111', '011011001': '101001010', '011011010': '001111111', '011011011': '010011010', '011011100': '000100010', '011011101': '011000111', '011011110': '111110010', '011011111': '100010111', '011100000': '001111000', '011100001': '010011101', '011100010': '110101000', '011100011': '101001101', '011100100': '111110101', '011100101': '100010000', '011100110': '000100101', '011100111': '011000000', '011101000': '101001100', '011101001': '110101001', '011101010': '010011100', '011101011': '001111001', '011101100': '011000001', '011101101': '000100100', '011101110': '100010001', '011101111': '111110100', '011110000': '011000010', '011110001': '000100111', '011110010': '100010010', '011110011': '111110111', '011110100': '101001111', '011110101': '110101010', '011110110': '010011111', '011110111': '001111010', '011111000': '111110110', '011111001': '100010011', '011111010': '000100110', '011111011': '011000011', '011111100': '001111011', '011111101': '010011110', '011111110': '110101011', '011111111': '101001110', '100000000': '000011011', '100000001': '011111110', '100000010': '111001011', '100000011': '100101110', '100000100': '110010110', '100000101': '101110011', '100000110': '001000110', '100000111': '010100011', '100001000': '100101111', '100001001': '111001010', '100001010': '011111111', '100001011': '000011010', '100001100': '010100010', '100001101': '001000111', '100001110': '101110010', '100001111': '110010111', '100010000': '010100001', '100010001': '001000100', '100010010': '101110001', '100010011': '110010100', '100010100': '100101100', '100010101': '111001001', '100010110': '011111100', '100010111': '000011001', '100011000': '110010101', '100011001': '101110000', '100011010': '001000101', '100011011': '010100000', '100011100': '000011000', '100011101': '011111101', '100011110': '111001000', '100011111': '100101101', '100100000': '001000010', '100100001': '010100111', '100100010': '110010010', '100100011': '101110111', '100100100': '111001111', '100100101': '100101010', '100100110': '000011111', '100100111': '011111010', '100101000': '101110110', '100101001': '110010011', '100101010': '010100110', '100101011': '001000011', '100101100': '011111011', '100101101': '000011110', '100101110': '100101011', '100101111': '111001110', '100110000': '011111000', '100110001': '000011101', '100110010': '100101000', '100110011': '111001101', '100110100': '101110101', '100110101': '110010000', '100110110': '010100101', '100110111': '001000000', '100111000': '111001100', '100111001': '100101001', '100111010': '000011100', '100111011': '011111001', '100111100': '001000001', '100111101': '010100100', '100111110': '110010001', '100111111': '101110100', '101000000': '101111000', '101000001': '110011101', '101000010': '010101000', '101000011': '001001101', '101000100': '011110101', '101000101': '000010000', '101000110': '100100101', '101000111': '111000000', '101001000': '001001100', '101001001': '010101001', '101001010': '110011100', '101001011': '101111001', '101001100': '111000001', '101001101': '100100100', '101001110': '000010001', '101001111': '011110100', '101010000': '111000010', '101010001': '100100111', '101010010': '000010010', '101010011': '011110111', '101010100': '001001111', '101010101': '010101010', '101010110': '110011111', '101010111': '101111010', '101011000': '011110110', '101011001': '000010011', '101011010': '100100110', '101011011': '111000011', '101011100': '101111011', '101011101': '110011110', '101011110': '010101011', '101011111': '001001110', '101100000': '100100001', '101100001': '111000100', '101100010': '011110001', '101100011': '000010100', '101100100': '010101100', '101100101': '001001001', '101100110': '101111100', '101100111': '110011001', '101101000': '000010101', '101101001': '011110000', '101101010': '111000101', '101101011': '100100000', '101101100': '110011000', '101101101': '101111101', '101101110': '001001000', '101101111': '010101101', '101110000': '110011011', '101110001': '101111110', '101110010': '001001011', '101110011': '010101110', '101110100': '000010110', '101110101': '011110011', '101110110': '111000110', '101110111': '100100011', '101111000': '010101111', '101111001': '001001010', '101111010': '101111111', '101111011': '110011010', '101111100': '100100010', '101111101': '111000111', '101111110': '011110010', '101111111': '000010111', '110000000': '000001100', '110000001': '011101001', '110000010': '111011100', '110000011': '100111001', '110000100': '110000001', '110000101': '101100100', '110000110': '001010001', '110000111': '010110100', '110001000': '100111000', '110001001': '111011101', '110001010': '011101000', '110001011': '000001101', '110001100': '010110101', '110001101': '001010000', '110001110': '101100101', '110001111': '110000000', '110010000': '010110110', '110010001': '001010011', '110010010': '101100110', '110010011': '110000011', '110010100': '100111011', '110010101': '111011110', '110010110': '011101011', '110010111': '000001110', '110011000': '110000010', '110011001': '101100111', '110011010': '001010010', '110011011': '010110111', '110011100': '000001111', '110011101': '011101010', '110011110': '111011111', '110011111': '100111010', '110100000': '001010101', '110100001': '010110000', '110100010': '110000101', '110100011': '101100000', '110100100': '111011000', '110100101': '100111101', '110100110': '000001000', '110100111': '011101101', '110101000': '101100001', '110101001': '110000100', '110101010': '010110001', '110101011': '001010100', '110101100': '011101100', '110101101': '000001001', '110101110': '100111100', '110101111': '111011001', '110110000': '011101111', '110110001': '000001010', '110110010': '100111111', '110110011': '111011010', '110110100': '101100010', '110110101': '110000111', '110110110': '010110010', '110110111': '001010111', '110111000': '111011011', '110111001': '100111110', '110111010': '000001011', '110111011': '011101110', '110111100': '001010110', '110111101': '010110011', '110111110': '110000110', '110111111': '101100011', '111000000': '101101111', '111000001': '110001010', '111000010': '010111111', '111000011': '001011010', '111000100': '011100010', '111000101': '000000111', '111000110': '100110010', '111000111': '111010111', '111001000': '001011011', '111001001': '010111110', '111001010': '110001011', '111001011': '101101110', '111001100': '111010110', '111001101': '100110011', '111001110': '000000110', '111001111': '011100011', '111010000': '111010101', '111010001': '100110000', '111010010': '000000101', '111010011': '011100000', '111010100': '001011000', '111010101': '010111101', '111010110': '110001000', '111010111': '101101101', '111011000': '011100001', '111011001': '000000100', '111011010': '100110001', '111011011': '111010100', '111011100': '101101100', '111011101': '110001001', '111011110': '010111100', '111011111': '001011001', '111100000': '100110110', '111100001': '111010011', '111100010': '011100110', '111100011': '000000011', '111100100': '010111011', '111100101': '001011110', '111100110': '101101011', '111100111': '110001110', '111101000': '000000010', '111101001': '011100111', '111101010': '111010010', '111101011': '100110111', '111101100': '110001111', '111101101': '101101010', '111101110': '001011111', '111101111': '010111010', '111110000': '110001100', '111110001': '101101001', '111110010': '001011100', '111110011': '010111001', '111110100': '000000001', '111110101': '011100100', '111110110': '111010001', '111110111': '100110100', '111111000': '010111000', '111111001': '001011101', '111111010': '101101000', '111111011': '110001101', '111111100': '100110101', '111111101': '111010000', '111111110': '011100101', '111111111': '000000000'}
print(d['001011111'])
for k, v in d.items():
    a, b = '{', '}'
    print(f'{a}"{k}", "{v}" {b},')
print(s)
# d = {}
# for i in range(512):
#     e = f"{i:09b}"
#     ne = dfs(e)
#     d[e] = ne
# print(d)

tests =      ( (0x05F, 0x100),
        (0x145,0x010),
(0x02F,0x080),
 (0x0EE,0x111),
(0x155,0x0AA),
(0x0BA, 0x145))
for x, y in tests:
    s = f"{x:09b}"
    ns = int(d[s], 2)
    print(hex(y), s, d[s], hex(ns))