-
Notifications
You must be signed in to change notification settings - Fork 14
/
two-tiling.py
261 lines (237 loc) · 77.4 KB
/
two-tiling.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
# Copyright (c) 2019 kamyu. All rights reserved.
#
# Google Code Jam 2018 World Finals - Problem B. Two-Tiling
# https://codingcompetitions.withgoogle.com/codejam/round/0000000000007766/000000000004da97
#
# Time: O((1+8+8+65)^(N^2)), required to precompute LOOKUP around 40 seconds by PyPy2
# Space: O(2^(2 * M^2 - 1) * N^2)
#
from collections import deque
from itertools import izip
def has_bit(bits, i):
return bits&BITMASKS[i] != 0
def reflect(pattern):
result = []
bitmask = BITMASKS[M]-1
for _ in xrange(M):
result.append(pattern & bitmask)
pattern >>= M
return int("".join(map(lambda x: format(x, "0{}b".format(M)), result)), 2)
def rotate(pattern): # ccw rotate
tmp = []
bitmask = BITMASKS[M]-1
for _ in xrange(M):
tmp.append(pattern & bitmask)
pattern >>= M
result = [0]*M
for j, bits in enumerate(tmp):
for i in xrange(M):
if has_bit(bits, i):
result[i] |= BITMASKS[j]
return int("".join(map(lambda x: format(x, "0{}b".format(M)), result)), 2)
def shift(pattern): # shift to left-up most
assert(pattern != 0)
result = deque()
bitmask = BITMASKS[M]-1
for _ in xrange(M):
result.append(pattern & bitmask)
pattern >>= M
count = 0
for j in xrange(M):
if any(has_bit(bits, j) for bits in result):
break
count += 1
while not result[0]:
result.rotate(-1)
result.reverse()
return int("".join(map(lambda x: format(x>>count, "0{}b".format(M)), result)), 2)
def get_patterns(pattern):
result = set()
for is_reflect in [False, True]:
if is_reflect:
pattern = reflect(pattern)
for _ in xrange(ROTATE_CYCLE):
result.add(shift(pattern))
pattern = rotate(pattern)
return tuple(sorted(result))
def add_pattern(state, pos, pattern):
for j in xrange(M):
if has_bit(pattern, j):
break
r, c = divmod(pos, N)
if c < j: # out of board
return 0
c -= j
for i in xrange(M):
for j in xrange(M):
if not has_bit(pattern, i*M+j):
continue
if r+i >= N or c+j >= N or has_bit(state, (r+i)*N+(c+j)):
return 0
state |= BITMASKS[(r+i)*N+(c+j)]
return state
def backtracking(patterns1, patterns2, curr, curr_state1, curr_state2, result1, result2, is_visited):
if (curr, curr_state1[0], curr_state2[0]) in is_visited:
return False
is_visited.add((curr, curr_state1[0], curr_state2[0]))
if curr == N and curr_state1[0] == curr_state2[0] == 0:
return False # no state in the first row, like shift up, impossible in the following search
if curr_state1[0] == curr_state2[0] != 0:
return True # find a solution, right away return
if curr == N*N:
return False # search to the end
has_pattern1, has_pattern2 = has_bit(curr_state1[0], curr), has_bit(curr_state2[0], curr)
if has_pattern1 and has_pattern2: # A, B
return backtracking(patterns1, patterns2, curr+1, curr_state1, curr_state2, result1, result2, is_visited)
if not has_pattern1 and not has_pattern2: # empty
if backtracking(patterns1, patterns2, curr+1, curr_state1, curr_state2, result1, result2, is_visited):
return True
choices1, choices2 = [0], [0]
if not has_pattern1:
choices1 = patterns1
if not has_pattern2:
choices2 = patterns2
for c1 in choices1:
if c1:
next_state1 = add_pattern(curr_state1[0], curr, c1)
if not next_state1:
continue
prev_state1 = curr_state1[0]
curr_state1[0] = next_state1
result1.append(c1)
for c2 in choices2:
if c2:
next_state2 = add_pattern(curr_state2[0], curr, c2)
if not next_state2:
continue
prev_state2 = curr_state2[0]
curr_state2[0] = next_state2
result2.append(c2)
if backtracking(patterns1, patterns2, curr+1, curr_state1, curr_state2, result1, result2, is_visited):
return True
if c2:
result2.pop()
curr_state2[0] = prev_state2
if c1:
result1.pop()
curr_state1[0] = prev_state1
return False
def get_placement(state, choices):
result = []
bitmask = BITMASKS[N]-1
for _ in xrange(N):
result.append(state & bitmask)
state >>= N
result = map(lambda x: list(format(x, "0{}b".format(N))[::-1].replace('0', '.').replace('1', '@')), result)
pos = 0
for k, pattern in enumerate(choices):
while pos != len(BITMASKS):
r, c = divmod(pos, N)
pos += 1
if result[r][c] == '@':
break
for j in xrange(M):
if has_bit(pattern, j):
break
c -= j
for i in xrange(M):
for j in xrange(M):
if not has_bit(pattern, i*M+j):
continue
result[r+i][c+j] = CHAR_SET[k]
return map(lambda x: "".join(x), result)
def is_possible(pattern1, pattern2):
def count_of_one(n):
result = 0
while n:
n &= n-1
result += 1
return result
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a//gcd(a, b)*b
return lcm(*map(count_of_one, [pattern1, pattern2])) <= N*N
def get_result(patterns):
patterns1, patterns2 = map(get_patterns, patterns)
is_swapped = False
if patterns1[0] > patterns2[0]:
is_swapped = True
patterns1, patterns2 = patterns2, patterns1
if (patterns1[0], patterns2[0]) not in LOOKUP:
LOOKUP[patterns1[0], patterns2[0]] = []
start, state1, state2, result1, result2 = 0, [0], [0], [], []
if is_possible(patterns1[0], patterns2[0]) and \
backtracking(patterns1, patterns2, start, state1, state2, result1, result2, set()):
LOOKUP[patterns1[0], patterns2[0]] = [get_placement(state1[0], result1), get_placement(state2[0], result2)]
result = list(LOOKUP[patterns1[0], patterns2[0]])
if is_swapped:
result.reverse()
return "IMPOSSIBLE" if not result else \
"\n".join(["POSSIBLE", "\n".join(" ".join(pair) for pair in izip(*result))])
def two_tiling():
pattern1, pattern2 = [0 for _ in xrange(M)], [0 for _ in xrange(M)]
for i in xrange(M):
pattern1[i], pattern2[i] = raw_input().strip().split(' ')
return get_result(map(lambda x: int("".join(x).replace('.', '0').replace('@', '1')[::-1], 2), [pattern1, pattern2]))
N, M = 8, 3
CHAR_SET = "!?0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
ROTATE_CYCLE = 4
BITMASKS = [0]*(N*N)
bitmask = 1
for i in xrange(len(BITMASKS)):
BITMASKS[i] = bitmask
bitmask <<= 1
'''
# precompute LOOKUP
class UnionFind(object):
def __init__(self, n):
self.set = range(n)
self.count = n
def find_set(self, x):
if self.set[x] != x:
self.set[x] = self.find_set(self.set[x]) # path compression.
return self.set[x]
def union_set(self, x, y):
x_root, y_root = map(self.find_set, (x, y))
if x_root == y_root:
return False
self.set[max(x_root, y_root)] = min(x_root, y_root)
self.count -= 1
return True
def is_valid_pattern(pattern):
idxs = {}
for i in xrange(M):
for j in xrange(M):
if not has_bit(pattern, i*M+j):
continue
idxs[i*M+j] = len(idxs)
union_find = UnionFind(len(idxs))
for i in xrange(M):
for j in xrange(M):
if not has_bit(pattern, i*M+j):
continue
for di, dj in [(-1, 0), (0, -1)]:
ni, nj = i+di, j+dj
if not (0 <= ni and 0 <= nj and has_bit(pattern, ni*M+nj)):
continue
union_find.union_set(idxs[i*M+j], idxs[ni*M+nj])
return union_find.count == 1
LOOKUP = {}
valid_set = set()
for i in xrange(1, BITMASKS[M*M]):
if is_valid_pattern(i):
valid_set.add(get_patterns(i)[0])
valid_patterns = list(valid_set)
for i in xrange(len(valid_patterns)):
for j in xrange(i+1, len(valid_patterns)):
get_result([valid_patterns[i], valid_patterns[j]])
print LOOKUP
exit()
'''
LOOKUP = {(1, 3): [['.......!', '.......?', '........', '........', '........', '........', '........', '........'], ['.......!', '.......!', '........', '........', '........', '........', '........', '........']], (1, 7): [['.......!', '.......?', '.......0', '........', '........', '........', '........', '........'], ['.......!', '.......!', '.......!', '........', '........', '........', '........', '........']], (1, 11): [['.......!', '......?0', '........', '........', '........', '........', '........', '........'], ['.......!', '......!!', '........', '........', '........', '........', '........', '........']], (1, 15): [['.......!', '.....?01', '........', '........', '........', '........', '........', '........'], ['.......!', '.....!!!', '........', '........', '........', '........', '........', '........']], (1, 23): [['.......!', '......?0', '.......1', '........', '........', '........', '........', '........'], ['.......!', '......!!', '.......!', '........', '........', '........', '........', '........']], (1, 27): [['......!?', '......01', '........', '........', '........', '........', '........', '........'], ['......!!', '......!!', '........', '........', '........', '........', '........', '........']], (1, 30): [['.......!', '......?0', '......1.', '........', '........', '........', '........', '........'], ['.......!', '......!!', '......!.', '........', '........', '........', '........', '........']], (1, 31): [['.......!', '......?0', '......12', '........', '........', '........', '........', '........'], ['.......!', '......!!', '......!!', '........', '........', '........', '........', '........']], (1, 47): [['......!?', '......0.', '......12', '........', '........', '........', '........', '........'], ['......!!', '......!.', '......!!', '........', '........', '........', '........', '........']], (1, 63): [['......!?', '......01', '......23', '........', '........', '........', '........', '........'], ['......!!', '......!!', '......!!', '........', '........', '........', '........', '........']], (1, 79): [['.......!', '.......?', '.....012', '........', '........', '........', '........', '........'], ['.......!', '.......!', '.....!!!', '........', '........', '........', '........', '........']], (1, 94): [['.......!', '......?0', '.....12.', '........', '........', '........', '........', '........'], ['.......!', '......!!', '.....!!.', '........', '........', '........', '........', '........']], (1, 95): [['.......!', '......?0', '.....123', '........', '........', '........', '........', '........'], ['.......!', '......!!', '.....!!!', '........', '........', '........', '........', '........']], (1, 111): [['.......!', '.....?.0', '.....123', '........', '........', '........', '........', '........'], ['.......!', '.....!.!', '.....!!!', '........', '........', '........', '........', '........']], (1, 121): [['.......!', '.....?01', '.......2', '........', '........', '........', '........', '........'], ['.......!', '.....!!!', '.......!', '........', '........', '........', '........', '........']], (1, 122): [['.......!', '.....?01', '......2.', '........', '........', '........', '........', '........'], ['.......!', '.....!!!', '......!.', '........', '........', '........', '........', '........']], (1, 123): [['.......!', '.....?01', '......23', '........', '........', '........', '........', '........'], ['.......!', '.....!!!', '......!!', '........', '........', '........', '........', '........']], (1, 124): [['.......!', '.....?01', '.....2..', '........', '........', '........', '........', '........'], ['.......!', '.....!!!', '.....!..', '........', '........', '........', '........', '........']], (1, 125): [['.......!', '.....?01', '.....2.3', '........', '........', '........', '........', '........'], ['.......!', '.....!!!', '.....!.!', '........', '........', '........', '........', '........']], (1, 126): [['.......!', '.....?01', '.....23.', '........', '........', '........', '........', '........'], ['.......!', '.....!!!', '.....!!.', '........', '........', '........', '........', '........']], (1, 127): [['.......!', '.....?01', '.....234', '........', '........', '........', '........', '........'], ['.......!', '.....!!!', '.....!!!', '........', '........', '........', '........', '........']], (1, 186): [['......!.', '.....?01', '......2.', '........', '........', '........', '........', '........'], ['......!.', '.....!!!', '......!.', '........', '........', '........', '........', '........']], (1, 187): [['......!?', '.....012', '......3.', '........', '........', '........', '........', '........'], ['......!!', '.....!!!', '......!.', '........', '........', '........', '........', '........']], (1, 189): [['......!.', '.....?01', '.....2.3', '........', '........', '........', '........', '........'], ['......!.', '.....!!!', '.....!.!', '........', '........', '........', '........', '........']], (1, 191): [['......!?', '.....012', '......34', '........', '........', '........', '........', '........'], ['......!!', '.....!!!', '......!!', '........', '........', '........', '........', '........']], (1, 239): [['......!?', '.....0.1', '.....234', '........', '........', '........', '........', '........'], ['......!!', '.....!.!', '.....!!!', '........', '........', '........', '........', '........']], (1, 247): [['......!?', '.....012', '.....3.4', '........', '........', '........', '........', '........'], ['......!!', '.....!!!', '.....!.!', '........', '........', '........', '........', '........']], (1, 254): [['......!?', '.....012', '.....34.', '........', '........', '........', '........', '........'], ['......!!', '.....!!!', '.....!!.', '........', '........', '........', '........', '........']], (1, 255): [['......!?', '.....012', '.....345', '........', '........', '........', '........', '........'], ['......!!', '.....!!!', '.....!!!', '........', '........', '........', '........', '........']], (1, 367): [['.....!?0', '.....1.2', '.....3.4', '........', '........', '........', '........', '........'], ['.....!!!', '.....!.!', '.....!.!', '........', '........', '........', '........', '........']], (1, 381): [['.....!.?', '.....012', '.....3.4', '........', '........', '........', '........', '........'], ['.....!.!', '.....!!!', '.....!.!', '........', '........', '........', '........', '........']], (1, 383): [['.....!?0', '.....123', '.....4.5', '........', '........', '........', '........', '........'], ['.....!!!', '.....!!!', '.....!.!', '........', '........', '........', '........', '........']], (1, 495): [['.....!?0', '.....1.2', '.....345', '........', '........', '........', '........', '........'], ['.....!!!', '.....!.!', '.....!!!', '........', '........', '........', '........', '........']], (1, 511): [['.....!?0', '.....123', '.....456', '........', '........', '........', '........', '........'], ['.....!!!', '.....!!!', '.....!!!', '........', '........', '........', '........', '........']], (3, 7): [['.......!', '.......!', '.......?', '.......?', '.......0', '.......0', '........', '........'], ['.......!', '.......!', '.......!', '.......?', '.......?', '.......?', '........', '........']], (3, 11): [['.......!', '......?!', '......?0', '......10', '......12', '.......2', '......33', '........'], ['.......!', '......!!', '......??', '......?0', '......00', '.......1', '......11', '........']], (3, 15): [['.......!', '.....??!', '........', '........', '........', '........', '........', '........'], ['.......!', '.....!!!', '........', '........', '........', '........', '........', '........']], (3, 23): [['.......!', '......?!', '......?0', '.....110', '........', '........', '........', '........'], ['.......!', '......!!', '......?!', '.....???', '........', '........', '........', '........']], (3, 27): [['......!!', '......??', '........', '........', '........', '........', '........', '........'], ['......!!', '......!!', '........', '........', '........', '........', '........', '........']], (3, 30): [['.......!', '......?!', '......?.', '........', '........', '........', '........', '........'], ['.......!', '......!!', '......!.', '........', '........', '........', '........', '........']], (3, 31): [['.......!', '......?!', '......?0', '.......0', '......11', '......22', '........', '........'], ['.......!', '......!!', '......!!', '.......?', '......??', '......??', '........', '........']], (3, 47): [['......!!', '......?.', '......?0', '......10', '......1.', '......22', '........', '........'], ['......!!', '......!.', '......!!', '......??', '......?.', '......??', '........', '........']], (3, 63): [['......!!', '......??', '......00', '........', '........', '........', '........', '........'], ['......!!', '......!!', '......!!', '........', '........', '........', '........', '........']], (3, 79): [['.......!', '.......!', '.....??0', '.......0', '.......1', '.....221', '........', '........'], ['.......!', '.......!', '.....!!!', '.......?', '.......?', '.....???', '........', '........']], (3, 94): [['.......!', '......?!', '.....0?.', '.....011', '....2233', '....4455', '......66', '.....77.'], ['.......!', '......!!', '.....!!.', '.....??0', '....??00', '....?001', '......11', '.....11.']], (3, 95): [['.......!', '......?!', '.....0?1', '.....021', '.....32.', '.....3..', '........', '........'], ['.......!', '......!!', '.....!!!', '.....???', '.....??.', '.....?..', '........', '........']], (3, 111): [['.......!', '.....?.!', '.....?00', '........', '........', '........', '........', '........'], ['.......!', '.....!.!', '.....!!!', '........', '........', '........', '........', '........']], (3, 121): [['.......!', '.....??!', '.......0', '.......0', '.....112', '.......2', '........', '........'], ['.......!', '.....!!!', '.......!', '.......?', '.....???', '.......?', '........', '........']], (3, 122): [['.......!', '.....??!', '......00', '.....122', '.....13.', '....4435', '....6675', '......7.'], ['.......!', '.....!!!', '......!?', '.....???', '.....0?.', '....0001', '....0111', '......1.']], (3, 123): [['.......!', '.....??!', '......00', '........', '........', '........', '........', '........'], ['.......!', '.....!!!', '......!!', '........', '........', '........', '........', '........']], (3, 124): [['.......!', '.....??!', '.....00.', '....1122', '....3344', '.....55.', '....677.', '....6...'], ['.......!', '.....!!!', '.....!?.', '....???0', '....?000', '.....01.', '....111.', '....1...']], (3, 125): [['.......!', '.....??!', '.....0.1', '.....0.1', '.....223', '....44.3', '..566778', '..5.99.8'], ['.......!', '.....!!!', '.....!.!', '.....?.?', '.....???', '....0?.1', '..000111', '..0.01.1']], (3, 126): [['.......!', '.....??!', '.....00.', '........', '........', '........', '........', '........'], ['.......!', '.....!!!', '.....!!.', '........', '........', '........', '........', '........']], (3, 127): [['.......!', '.....??!', '.....001', '.......1', '.....223', '.....443', '........', '........'], ['.......!', '.....!!!', '.....!!!', '.......?', '.....???', '.....???', '........', '........']], (3, 186): [['.....!..', '...??!0.', '..11220.', '...34455', '...3677.', '....6...', '........', '........'], ['.....!..', '...?!!!.', '..???!0.', '...?1000', '...1110.', '....1...', '........', '........']], (3, 187): [['......!!', '.....?00', '.....?1.', '....221.', '....33..', '........', '........', '........'], ['......!!', '.....!!!', '.....?!.', '....???.', '....??..', '........', '........', '........']], (3, 189): [['......!!', '.....??.', '......00', '........', '........', '........', '........', '........'], ['......!!', '.....!!.', '......!!', '........', '........', '........', '........', '........']], (3, 191): [['......!!', '.....??0', '......10', '......12', '.....332', '......44', '........', '........'], ['......!!', '.....!!!', '......!!', '......??', '.....???', '......??', '........', '........']], (3, 239): [['......!!', '.....?.0', '.....?10', '......12', '.....3.2', '.....344', '........', '........'], ['......!!', '.....!.!', '.....!!!', '......??', '.....?.?', '.....???', '........', '........']], (3, 247): [['......!!', '.....??0', '.....1.0', '.....122', '......33', '.....44.', '........', '........'], ['......!!', '.....!!!', '.....!.!', '.....???', '......??', '.....??.', '........', '........']], (3, 254): [['......!!', '.....?00', '.....?1.', '......12', '.....332', '.....44.', '........', '........'], ['......!!', '.....!!!', '.....!!.', '......??', '.....???', '.....??.', '........', '........']], (3, 255): [['......!!', '.....??0', '.....110', '........', '........', '........', '........', '........'], ['......!!', '.....!!!', '.....!!!', '........', '........', '........', '........', '........']], (3, 367): [['.....!!?', '.....0.?', '.....0.1', '.....221', '.....3.4', '.....3.4', '........', '........'], ['.....!!!', '.....!.!', '.....!.!', '.....???', '.....?.?', '.....?.?', '........', '........']], (3, 381): [['....!.?.', '....!0?.', '....1022', '..3.1445', '..3667.5', '..8897..', '...a9b..', '...a.b..'], ['....!.!.', '....!!!.', '....!?!?', '..0.0???', '..000?.?', '..0101..', '...111..', '...1.1..']], (3, 383): [['.....!!?', '.....00?', '.....1.2', '.....132', '.....435', '.....4.5', '........', '........'], ['.....!!!', '.....!!!', '.....!.!', '.....???', '.....???', '.....?.?', '........', '........']], (3, 495): [['.....!!?', '.....0.?', '.....011', '........', '........', '........', '........', '........'], ['.....!!!', '.....!.!', '.....!!!', '........', '........', '........', '........', '........']], (3, 511): [['.....!!?', '.....00?', '.....112', '.....332', '.....445', '.....665', '........', '........'], ['.....!!!', '.....!!!', '.....!!!', '.....???', '.....???', '.....???', '........', '........']], (7, 11): [['.......!', '......?!', '......?!', '......?.', '........', '........', '........', '........'], ['.......!', '......!!', '......??', '......?.', '........', '........', '........', '........']], (7, 15): [['.......!', '.....?0!', '.....?0!', '.....?0.', '....111.', '........', '........', '........'], ['.......!', '.....!!!', '.....???', '.....?0.', '....000.', '........', '........', '........']], (7, 23): [['.......!', '......?!', '......?!', '000111?2', '34555..2', '34..6662', '34777888', '..999...'], ['.......!', '......!!', '......?!', '01112???', '00122..3', '04..2533', '44465553', '..666...']], (7, 27): [['......!?', '......!?', '......!?', '......01', '......01', '......01', '........', '........'], ['......!!', '......!!', '......??', '......??', '......00', '......00', '........', '........']], (7, 30): [['.......!', '......?!', '......?!', '......?0', '......10', '......10', '......1.', '........'], ['.......!', '......!!', '......!?', '......??', '......?0', '......00', '......0.', '........']], (7, 31): [['.......!', '......?!', '......?!', '......?0', '.....120', '.....120', '.....12.', '........'], ['.......!', '......!!', '......!!', '......??', '.....???', '.....000', '.....00.', '........']], (7, 47): [['......!?', '.....0!?', '.....0!?', '.....01.', '.2223.1.', '4445361.', '777536..', '...5.6..'], ['......!!', '.....??!', '.....?!!', '.....??.', '.0001.1.', '2020111.', '222333..', '...3.3..']], (7, 63): [['......!?', '......!?', '......!?', '........', '........', '........', '........', '........'], ['......!!', '......!!', '......!!', '........', '........', '........', '........', '........']], (7, 79): [['.......!', '.......!', '.....?0!', '.....?01', '....2?01', '....2..1', '....2...', '........'], ['.......!', '.......!', '.....!!!', '.....???', '....000?', '....0..?', '....0...', '........']], (7, 94): [['.......!', '....???!', '...0001!', '...22213', '...44413', '...56663', '...5777.', '...5....'], ['.......!', '....??!!', '...??!!0', '...?1100', '...11002', '...13322', '...3322.', '...3....']], (7, 95): [['.......!', '......?!', '.....0?!', '....10?.', '....10..', '....1...', '........', '........'], ['.......!', '......!!', '.....!!!', '....???.', '....??..', '....?...', '........', '........']], (7, 111): [['.......!', '.....?.!', '.....?0!', '.....?01', '...22201', '....3331', '..444555', '........'], ['.......!', '.....!.!', '.....!!!', '.....???', '...00?11', '....0??1', '..000111', '........']], (7, 121): [['.......!', '....???!', '....000!', '....1...', '....1...', '....1...', '...222..', '........'], ['.......!', '....?!!!', '....???!', '....?...', '....0...', '....0...', '...000..', '........']], (7, 122): [['.......!', '....???!', '...0001!', '...22213', '...44413', '...56663', '...5777.', '...5....'], ['.......!', '....?!!!', '...???!0', '...?1000', '...11102', '...13222', '...3332.', '...3....']], (7, 123): [['.......!', '.....?0!', '.....?0!', '.....?01', '.2223331', '.4445551', '..666777', '........'], ['.......!', '.....!!!', '.....?!!', '.....???', '.0001??2', '.0011222', '..011122', '........']], (7, 124): [['.......!', '....???!', '..0111.!', '..0.2223', '..0444.3', '..5.6663', '..5777..', '..5.....'], ['.......!', '....?!!!', '..???!.0', '..?.1000', '..1110.2', '..1.3222', '..3332..', '..3.....']], (7, 125): [['.......!', '.....?0!', '.....?0!', '....1?0.', '....1222', '..3.1444', '..3555..', '..3.....'], ['.......!', '.....!!!', '.....!?!', '....???.', '....?0?0', '..1.1000', '..1110..', '..1.....']], (7, 126): [['.......!', '.....?0!', '.....?0!', '.....?01', '.....231', '.....231', '.....23.', '........'], ['.......!', '.....!!!', '.....!!?', '.....???', '.....??0', '.....000', '.....00.', '........']], (7, 127): [['.......!', '.....?0!', '.....?0!', '.....?01', '.....231', '.....231', '.....23.', '.....444'], ['.......!', '.....!!!', '.....!!!', '.....???', '.....???', '.....00?', '.....00.', '.....000']], (7, 186): [], (7, 187): [['.....!?.', '....0!?.', '...10!?.', '22210333', '4441555.', '.67888..', '.67999..', '.67.....'], ['.....!!.', '....!!!.', '...??!0.', '11???000', '111?200.', '.13222..', '.33322..', '.33.....']], (7, 189): [['......!.', '.....?!0', '.....?!0', '.....?10', '.....213', '.....213', '.....2.3', '........'], ['......!.', '.....!!!', '.....!?!', '.....???', '.....?0?', '.....000', '.....0.0', '........']], (7, 191): [['......!?', '.....0!?', '...120!?', '...120..', '...12...', '..333...', '..444...', '........'], ['......!!', '.....!!!', '...???!!', '...???..', '...0?...', '..000...', '..000...', '........']], (7, 239): [], (7, 247): [['......!?', '.....0!?', '....10!?', '....102.', '....1324', '.....324', '.....3.4', '........'], ['......!!', '.....!!!', '....?!?!', '....???.', '....??00', '.....000', '.....0.0', '........']], (7, 254): [], (7, 255): [['......!?', '.....0!?', '.....0!?', '.....012', '.....312', '...45312', '...453..', '...45...'], ['......!!', '.....!!!', '.....!!!', '.....???', '.....???', '...000??', '...000..', '...00...']], (7, 367): [['.....!!!', '....?000', '1.2.?333', '1.2.?45.', '162..457', '.6888457', '.6..9997', '.aaabbb.'], ['.....!!!', '....?!?!', '0.0.?!?!', '0.0.???.', '000..111', '.2223131', '.2..3131', '.222333.']], (7, 381): [], (7, 383): [['.....!!!', '.....???', '..0111.2', '..0333.2', '..0.4442', '.....555', '........', '........'], ['.....!!!', '.....!!!', '..???!.!', '..???0.0', '..?.?000', '.....000', '........', '........']], (7, 495): [], (7, 511): [['.....!!!', '.....???', '.....000', '........', '........', '........', '........', '........'], ['.....!!!', '.....!!!', '.....!!!', '........', '........', '........', '........', '........']], (11, 15): [['.......!', '.....?!!', '.....??0', '.....100', '....2113', '....2233', '....4455', '....4..5'], ['.......!', '.....!!!', '.....???', '.....?01', '....0001', '....2211', '....2333', '....2..3']], (11, 23): [['.......!', '......!!', '.......?', '.....0??', '.....00.', '....1122', '..331425', '...34455'], ['.......!', '......!!', '.......!', '.....???', '.....0?.', '....0001', '..222311', '...23331']], (11, 27): [['......!!', '......!?', '......??', '......00', '......01', '......11', '........', '........'], ['......!!', '......!!', '......??', '......??', '......00', '......00', '........', '........']], (11, 30): [['.......!', '......!!', '......??', '......?0', '......00', '......11', '......1.', '........'], ['.......!', '......!!', '......!?', '......??', '......?0', '......00', '......0.', '........']], (11, 31): [['.......!', '......!!', '......??', '......?0', '.....100', '.....112', '......22', '........'], ['.......!', '......!!', '......!!', '......??', '.....???', '.....000', '......00', '........']], (11, 47): [['......!!', '......!.', '......??', '......?0', '11223300', '1.2.3455', '6677445.', '6.7.....'], ['......!!', '......!.', '......!!', '......??', '0001122?', '0.0.12??', '3331122.', '3.3.....']], (11, 63): [['......!!', '......!?', '......??', '........', '........', '........', '........', '........'], ['......!!', '......!!', '......!!', '........', '........', '........', '........', '........']], (11, 79): [['.......!', '....??!!', '....?001', '....2011', '..33224.', '..35.44.', '..55677.', '...667..'], ['.......!', '....???!', '....?!!!', '....?000', '..11102.', '..13.02.', '..13222.', '...333..']], (11, 94): [['.......!', '......!!', '.....??.', '.....?00', '....1102', '.3344122', '.3546.77', '..55667.'], ['.......!', '......!!', '.....!!.', '.....??0', '....??00', '.122?003', '.1122.33', '..11233.']], (11, 95): [['.......!', '......!!', '.....??0', '.....?00', '.....11.', '.....1..', '........', '........'], ['.......!', '......!!', '.....!!!', '.....???', '.....??.', '.....?..', '........', '........']], (11, 111): [['......!!', '....??!0', '....?100', '....211.', '...22.3.', '.4.5533.', '.445....', '........'], ['......!!', '....???!', '....?!!!', '....??0.', '...10.0.', '.1.1000.', '.111....', '........']], (11, 121): [['.......!', '.....?!!', '....??00', '.....10.', '..22311.', '..233455', '..67445.', '.6677...'], ['.......!', '.....!!!', '....???!', '.....?0.', '..111?0.', '..213000', '..21333.', '.2223...']], (11, 122): [['.......!', '.....?!!', '.....??.', '....0011', '....0213', '..442233', '.5546677', '..5.6.7.'], ['.......!', '.....!!!', '.....?!.', '....???0', '....?000', '..112203', '.1122333', '..1.2.3.']], (11, 123): [['.......!', '.....?!!', '.....??0', '.....100', '.....11.', '........', '........', '........'], ['.......!', '.....!!!', '.....?!!', '.....???', '.....??.', '........', '........', '........']], (11, 124): [['.......!', '.....?!!', '.....??.', '....0011', '....0213', '..442233', '5546..7.', '5.66.77.'], ['.......!', '.....!!!', '.....!?.', '....???0', '....?000', '..122033', '1112..3.', '1.22.33.']], (11, 125): [['.......!', '.....?!!', '....0??1', '....0011', '....2233', '....2443', '....554.', '....5...'], ['.......!', '.....!!!', '....?!?!', '....???0', '....?000', '....1010', '....111.', '....1...']], (11, 126): [['.......!', '.....?!!', '.....??.', '........', '........', '........', '........', '........'], ['.......!', '.....!!!', '.....!!.', '........', '........', '........', '........', '........']], (11, 127): [['.......!', '.....?!!', '.....??0', '......00', '...11223', '...14233', '...44...', '........'], ['.......!', '.....!!!', '.....!!!', '......??', '...000??', '...00???', '...00...', '........']], (11, 186): [['......!.', '.....?!!', '.....??.', '...0011.', '.220314.', '55233644', '.5.7766.', '....7...'], ['......!.', '.....!!!', '.....?!.', '...0???.', '.1000?2.', '11103222', '.1.3332.', '....3...']], (11, 187): [['......!!', '.....??!', '.....?0.', '....100.', '....11..', '........', '........', '........'], ['......!!', '.....!!!', '.....?!.', '....???.', '....??..', '........', '........', '........']], (11, 189): [['......!!', '.....?!.', '...0.??1', '...00211', '....322.', '....3344', '.....54.', '....55..'], ['......!!', '.....!!.', '...?.?!!', '...???00', '....?00.', '....1100', '.....11.', '....11..']], (11, 191): [['......!!', '.....?!0', '....??00', '....112.', '....1322', '.....334', '......44', '........'], ['......!!', '.....!!!', '....??!!', '....???.', '....??00', '.....000', '......00', '........']], (11, 239): [['......!!', '.....?.!', '.....??0', '......00', '.....1.2', '..331122', '..3.4...', '...44...'], ['......!!', '.....!.!', '.....!!!', '......??', '.....?.?', '..000???', '..0.0...', '...00...']], (11, 247): [['......!!', '.....?!0', '....??00', '....122.', '.33112..', '.34.....', '..44....', '........'], ['......!!', '.....!!!', '....?!?!', '....???.', '.000??..', '.00.....', '..00....', '........']], (11, 254): [['......!!', '.....??!', '.....?0.', '......00', '.....122', '...3112.', '..433...', '..44....'], ['......!!', '.....!!!', '.....!!.', '......??', '.....???', '...00??.', '..000...', '..00....']], (11, 255): [['......!!', '.....?!0', '...1??00', '...112..', '...322..', '...334..', '...544..', '...55...'], ['......!!', '.....!!!', '...??!!!', '...???..', '...???..', '...000..', '...000..', '...00...']], (11, 367): [['.....!!?', '....0!??', '....0011', '....221.', '.334255.', '66344577', '6899aa7b', '889..abb'], ['.....!!!', '....?!?!', '....?!?!', '....???.', '.000111.', '20201313', '20201313', '222..333']], (11, 381): [['.....!.?', '..00!!??', '1102.3.4', '.1223344', '5566778.', '5.6.7988', 'aabb99..', 'a.b.....'], ['.....!.!', '..???!!!', '000?.!.!', '.0???111', '0002221.', '3.3.2111', '333222..', '3.3.....']], (11, 383): [['.....!!?', '.....!??', '.....0.1', '..220011', '..23.455', '..3344.5', '........', '........'], ['.....!!!', '.....!!!', '.....!.!', '..???000', '..??.000', '..???0.0', '........', '........']], (11, 495): [], (11, 511): [['.....!!?', '.....!??', '.....001', '.....011', '.....223', '.....233', '........', '........'], ['.....!!!', '.....!!!', '.....!!!', '.....???', '.....???', '.....???', '........', '........']], (15, 23): [['.......!', '.....!!!', '....???0', '....?000', '.....111', '.......1', '........', '........'], ['.......!', '.....?!!', '....???!', '....0001', '.....011', '.......1', '........', '........']], (15, 27): [['......!?', '....!!!?', '....01??', '..000111', '..2223..', '.423335.', '.444555.', '........'], ['......!!', '....??!!', '....??00', '..112200', '..1122..', '.334455.', '.334455.', '........']], (15, 30): [['.......!', '.....!!!', '....???.', '....?...', '........', '........', '........', '........'], ['.......!', '.....?!!', '....??!.', '....?...', '........', '........', '........', '........']], (15, 31): [['.......!', '.....!!!', '....???0', '....?000', '.....111', '.....12.', '....222.', '........'], ['.......!', '.....?!!', '....??!!', '....??00', '.....000', '.....11.', '....111.', '........']], (15, 47): [['......!?', '...0!!!?', '..1000??', '..11123.', '..42223.', '.5444633', '.5557666', '..777...'], ['......!!', '...??00!', '..11?0!!', '..1??00.', '..11222.', '.3332424', '.3535444', '..555...']], (15, 63): [['......!?', '....!!!?', '....01??', '..000111', '..223334', '..253444', '.62555..', '.666....'], ['......!!', '....??!!', '....??!!', '..00??11', '..002211', '..002211', '.33322..', '.333....']], (15, 79): [['.......!', '....?!!!', '....???0', '....1000', '22111333', '2..45553', '2444675.', '..666777'], ['.......!', '....???!', '....?!!!', '....?000', '11123330', '1..24530', '1222453.', '..444555']], (15, 94): [['.......!', '....?!!!', '...0???.', '...000..', '...11...', '...21...', '...21...', '..22....'], ['.......!', '....??!!', '...??!!.', '...?00..', '...00...', '...01...', '...11...', '..11....']], (15, 95): [['.......!', '...??!!!', '...?0001', '...?0111', '....2223', '....2333', '........', '........'], ['.......!', '...???!!', '...??!!!', '...?0001', '....0011', '....0111', '........', '........']], (15, 111): [['.......!', '.....?.!', '...???!!', '...0001.', '...0111.', '.....222', '.....2.3', '.....333'], ['.......!', '.....!.!', '...??!!!', '...?000.', '...???0.', '.....001', '.....1.1', '.....111']], (15, 121): [['.......!', '.....!!!', '.......?', '.....???', '......0.', '....000.', '..111222', '....12..'], ['.......!', '.....!!!', '.......!', '.....???', '......?.', '....01?.', '..000111', '....01..']], (15, 122): [['.......!', '.....!!!', '......?.', '....???.', '...00011', '...0.21.', '.....21.', '....22..'], ['.......!', '.....!!!', '......!.', '....?00.', '...???00', '...?.10.', '.....11.', '....11..']], (15, 123): [['.......!', '.....!!!', '......?0', '....???0', '...12.00', '.111222.', '.333....', '.3......'], ['.......!', '.....!!!', '......!!', '....?000', '...??.00', '.11???0.', '.111....', '.1......']], (15, 124): [['.......!', '.....!!!', '.....?..', '.....???', '...0001.', '...0111.', '..222...', '..2.....'], ['.......!', '.....!!!', '.....!..', '.....?00', '...???0.', '...?100.', '..111...', '..1.....']], (15, 125): [['.......!', '.....!!!', '.....???', '....0?1.', '....0.1.', '....0011', '..222.3.', '..2.333.'], ['.......!', '.....!!!', '.....!?!', '....???.', '....?.?.', '....0111', '..000.1.', '..0.011.']], (15, 126): [['.......!', '.....!!!', '.....???', '.....?00', '.....10.', '...1110.', '..222333', '..2....3'], ['.......!', '.....!!!', '.....!!?', '.....???', '.....??.', '...0011.', '..000111', '..0....1']], (15, 127): [['.......!', '.....!!!', '.....???', '.....?00', '.....110', '...22210', '...23.14', '..333444'], ['.......!', '.....!!!', '.....!!!', '.....???', '.....???', '...00?11', '...00.11', '..000111']], (15, 186): [], (15, 187): [['......!.', '....!!!?', '...00???', '...01...', '...01...', '.22211..', '.2333...', '..3.....'], ['......!.', '....?!!!', '...???!!', '...??...', '...00...', '.11000..', '.1110...', '..1.....']], (15, 189): [['......!.', '...?!!!0', '.???.000', '11122233', '1.4442.3', '..45..63', '...5556.', '......66'], ['......!.', '...??!!!', '.0??.!1!', '000??111', '0.0221.1', '..22..33', '...2233.', '......33']], (15, 191): [['......!?', '....!!!?', '...000??', '...01112', '.....312', '.....322', '....433.', '....444.'], ['......!!', '....?!!!', '...???!!', '...???00', '.....000', '.....100', '....111.', '....111.']], (15, 239): [['......!!', '.....?.!', '..0???1!', '..0.1112', '.00333.2', '.4.3..22', '.444....', '........'], ['......!!', '.....!.!', '..???!!!', '..?.?000', '.11??0.0', '.1.1..00', '.111....', '........']], (15, 247): [['......!!', '.....?!.', '...???!0', '..111000', '..1.222.', '....2333', '.....34.', '....444.'], ['......!!', '.....!!.', '...??!!!', '..???000', '..?.?00.', '....1100', '.....11.', '....111.']], (15, 254): [], (15, 255): [['......!?', '...0!!!?', '..1000??', '..111...', '........', '........', '........', '........'], ['......!!', '...??!!!', '..???!!!', '..???...', '........', '........', '........', '........']], (15, 367): [['.....!!!', '.....!.?', '....0???', '.1000.2.', '.1..222.', '.113344.', '....3.4.', '....3.4.'], ['.....!!!', '.....!.!', '....?!?!', '.000?.?.', '.0..???.', '.000111.', '....1.1.', '....1.1.']], (15, 381): [], (15, 383): [['.....!!!', '.....!??', '.....0.?', '..1000.?', '11123334', '52223444', '555.....', '........'], ['.....!!!', '.....!!!', '.....!.!', '..???0.0', '111??000', '11???000', '111.....', '........']], (15, 495): [['.....!!!', '.....!.?', '.....???', '........', '........', '........', '........', '........'], ['.....!!!', '.....!.!', '.....!!!', '........', '........', '........', '........', '........']], (15, 511): [], (23, 27): [['....!!!?', '....0!??', '..10002?', '31114222', '33..44..', '35..46..', '555766..', '..7776..'], ['....!!??', '....!!??', '..001122', '33001122', '33..44..', '55..44..', '556677..', '..6677..']], (23, 30): [['.......!', '......!!', '......?!', '.....???', '....000.', '....10..', '....11..', '....1...'], ['.......!', '......!!', '......!?', '.....0??', '....00?.', '....01..', '....11..', '....1...']], (23, 31): [['.......!', '......!!', '......?!', '.....???', '.....01.', '...20011', '..22201.', '........'], ['.......!', '......!!', '......!!', '.....???', '.....??.', '...00111', '..00011.', '........']], (23, 47): [['.....!.?', '...0!!??', '11100!.?', '.1203444', '5223334.', '5526777.', '5.6667..', '........'], ['.....!.!', '...??!!!', '0011?2.2', '.01??222', '0011333.', '4445353.', '4.4555..', '........']], (23, 63): [['.....!!!', '.....?!0', '....??00', '....1?20', '....1122', '....132.', '....333.', '........'], ['.....!!!', '.....!!!', '....??00', '....??00', '....??00', '....111.', '....111.', '........']], (23, 79): [['......!.', '..???!!!', '..0?1112', '3000.122', '334.5552', '344465..', '777666..', '.7......'], ['......!.', '..?000!1', '..?0!!!1', '???0.111', '222.3444', '255534..', '253334..', '.5......']], (23, 94): [['.......!', '...?0.!!', '..??001!', '2.3?0.11', '2233.41.', '253.444.', '55.6777.', '.56667..'], ['.......!', '...??.!!', '..??0!!1', '2.?00.11', '2200.11.', '322.445.', '33.4455.', '.33455..']], (23, 95): [['.......!', '......!!', '.....?0!', '....??00', '12223?0.', '112333..', '1.......', '........'], ['.......!', '......!!', '.....!!!', '....?000', '111??00.', '11???0..', '1.......', '........']], (23, 111): [['.....!!!', '..?000!1', '..??0211', '..?32221', '..333...', '........', '........', '........'], ['.....!!!', '..???!00', '..?11!!0', '..??1000', '..111...', '........', '........', '........']], (23, 121): [['.......!', '.....?!!', '....???!', '.....0..', '...1.00.', '...1102.', '...1.222', '........'], ['.......!', '.....!!!', '....???!', '.....?..', '...0.?1.', '...0001.', '...0.111', '........']], (23, 122): [['.......!', '...???!!', '....?01!', '....0011', '.....01.', '.....222', '......2.', '........'], ['.......!', '...??!!!', '....??!0', '....?000', '.....10.', '.....111', '......1.', '........']], (23, 123): [['.......!', '.....?!!', '....???!', '....000.', '....102.', '...1122.', '...31.2.', '..333...'], ['.......!', '.....!!!', '....??!!', '....???.', '....?00.', '...1000.', '...11.0.', '..111...']], (23, 124): [['.....!..', '...?!!!.', '.0???12.', '.0031122', '4033312.', '4456667.', '455.677.', '..5...7.'], ['.....!..', '...!!!?.', '.00!???.', '.011?233', '0012223.', '4112533.', '444.555.', '..4...5.']], (23, 125): [['.......!', '.....?!!', '....???!', '....000.', '....10.2', '...11122', '....3..2', '...333..'], ['.......!', '.....!!!', '....?!?!', '....???.', '....?0.0', '...11000', '....1..0', '...111..']], (23, 126): [['.......!', '.....?!!', '...0???!', '..000111', '..22231.', '...233..', '.....3..', '........'], ['.......!', '.....!!!', '...??!!0', '..???000', '..?1100.', '...111..', '.....1..', '........']], (23, 127): [['.......!', '.....?!!', '....???!', '....000.', '....102.', '..31122.', '..33142.', '..3.444.'], ['.......!', '.....!!!', '....?!!!', '....???.', '....???.', '..00011.', '..00011.', '..0.111.']], (23, 186): [['.....!..', '....!!!.', '...?.01.', '..??0011', '...?.01.', '....222.', '.....2..', '........'], ['.....!..', '....!!!.', '...?.!0.', '..???000', '...?.10.', '....111.', '.....1..', '........']], (23, 187): [['......!.', '.....!!!', '....???.', '...01?..', '..0011..', '.2301...', '2233....', '.23.....'], ['......!.', '.....!!!', '....?!!.', '...???..', '..00??..', '.1000...', '1110....', '.11.....']], (23, 189): [['......!.', '.....!!!', '....?000', '...???0.', '..1222..', '.1112...', '.333....', '..3.....'], ['......!.', '.....!!!', '....?!?!', '...0???.', '..000?..', '.1010...', '.111....', '..1.....']], (23, 191): [['......!.', '.....!!!', '.....???', '......?0', '....1200', '.3411220', '334412..', '.34.....'], ['......!.', '.....!!!', '.....!!!', '......??', '....0???', '.11000??', '111000..', '.11.....']], (23, 239): [], (23, 247): [], (23, 254): [], (23, 255): [['.....!?.', '..01!!??', '20011!?3', '22014.33', '25554463', '..574666', '..777...', '........'], ['.....!!.', '..???!!!', '00???!!!', '000??.11', '00022111', '..222111', '..222...', '........']], (23, 367): [], (23, 381): [], (23, 383): [['.....!!!', '.....?!.', '.....??0', '.....?00', '......10', '.....111', '........', '........'], ['.....!!!', '.....!!.', '.....!!!', '.....???', '......??', '.....???', '........', '........']], (23, 495): [], (23, 511): [], (27, 30): [['.....!!.', '...??!!.', '...??00.', '...1100.', '...11.22', '....3322', '....33..', '........'], ['.....!!.', '...?!!0.', '...??00.', '...1?02.', '...11.22', '....1332', '....33..', '........']], (27, 31): [['......!!', '....??!!', '....??..', '....00..', '....00..', '....11..', '....1122', '......22'], ['......!!', '....?!!!', '....??..', '....??..', '....00..', '....00..', '....0111', '......11']], (27, 47): [], (27, 63): [['......!!', '......!!', '......??', '......??', '......00', '......00', '........', '........'], ['......!!', '......!!', '......!!', '......??', '......??', '......??', '........', '........']], (27, 79): [['....!!..', '....!!..', '..??0011', '..??0011', '....22..', '....22..', '........', '........'], ['....!?..', '....!?..', '..!!!???', '..000111', '....01..', '....01..', '........', '........']], (27, 94): [], (27, 95): [['....!!??', '....!!??', '....0011', '....0011', '....2233', '....2233', '........', '........'], ['....!!!?', '....!!??', '....!???', '....0001', '....0011', '....0111', '........', '........']], (27, 111): [['......!!', '....??!!', '....??00', '....1100', '....1122', '....3322', '....33..', '........'], ['......!!', '....???!', '....?!!!', '....??00', '....1110', '....1000', '....11..', '........']], (27, 121): [], (27, 122): [], (27, 123): [['......!!', '....??!!', '....??00', '....1100', '....1122', '....3322', '....33..', '........'], ['......!!', '....?!!!', '....???!', '....??00', '....1000', '....1110', '....11..', '........']], (27, 124): [['....!!..', '....!!..', '..??0011', '..??0011', '....22..', '....22..', '........', '........'], ['....!!..', '....!?..', '..0!!???', '..00011?', '....01..', '....11..', '........', '........']], (27, 125): [], (27, 126): [['......!!', '....??!!', '..00??..', '..00....', '........', '........', '........', '........'], ['......!!', '....?!!!', '..???!..', '..??....', '........', '........', '........', '........']], (27, 127): [['......!!', '......!!', '....??00', '..11??00', '..112233', '....2233', '....44..', '....44..'], ['......!!', '......!!', '....?!!!', '..???000', '..???000', '....1110', '....11..', '....11..']], (27, 186): [], (27, 187): [], (27, 189): [], (27, 191): [], (27, 239): [], (27, 247): [], (27, 254): [], (27, 255): [['......!!', '..??00!!', '..??0011', '..22..11', '..223344', '..553344', '..55....', '........'], ['......!!', '..???!!!', '..???!!!', '..??..00', '..111000', '..111000', '..11....', '........']], (27, 367): [], (27, 381): [], (27, 383): [], (27, 495): [], (27, 511): [['..!!??00', '..!!??00', '..112233', '..112233', '..445566', '..445566', '........', '........'], ['..!!!???', '..!!!???', '..!!!???', '..000111', '..000111', '..000111', '........', '........']], (30, 31): [['.......!', '......!!', '......!?', '......??', '......?0', '......00', '..11220.', '...1122.'], ['.......!', '......!!', '......!!', '......??', '......??', '......0?', '..11100.', '...1100.']], (30, 47): [['......!!', '.....!!?', '.....0??', '...100?.', '..110...', '..122...', '..22....', '........'], ['......!!', '.....??!', '.....?!!', '...00??.', '..110...', '..100...', '..11....', '........']], (30, 63): [['......!!', '...??!!0', '.1??2200', '.112230.', '.415533.', '4466553.', '466.....', '........'], ['......!!', '...???!!', '.00???!!', '.001122.', '.001122.', '3331122.', '333.....', '........']], (30, 79): [['......!.', '......!!', '....?00!', '....??00', '....1?..', '..2211..', '...221..', '........'], ['......!.', '......!?', '....!!!?', '....0???', '....01..', '..0001..', '...111..', '........']], (30, 94): [['.......!', '......!!', '.....?!.', '....??..', '..00?...', '.1100...', '11.22...', '..22....'], ['.......!', '......!!', '.....!!.', '....??..', '..0??...', '.00?1...', '00.11...', '..11....']], (30, 95): [['.......!', '....?.!!', '...??0!1', '..2?0011', '..22031.', '...233..', '....3...', '........'], ['.......!', '....?.!!', '...??!!!', '..???000', '..11100.', '...110..', '....1...', '........']], (30, 111): [['.....!!?', '.011!!??', '.00112?3', '.4052233', '4455263.', '4758866.', '7799886.', '799.....'], ['.....!!!', '.???0!11', '.?0?0!!1', '.?000111', '2223334.', '2553434.', '2253444.', '555.....']], (30, 121): [], (30, 122): [['.......!', '.....?!!', '....??!.', '...0?...', '..001...', '..011...', '.221....', '..22....'], ['.......!', '.....!!!', '....??!.', '...??...', '..00?...', '..100...', '.110....', '..11....']], (30, 123): [['.......!', '.....?!!', '....??!0', '....?100', '....1102', '....1322', '....332.', '....3...'], ['.......!', '.....!!!', '....??!!', '....???0', '....?000', '....1100', '....111.', '....1...']], (30, 124): [['......!.', '....??!!', '...??00!', '.12200..', '.1122...', '..1.....', '........', '........'], ['......!.', '....!!!?', '...0!???', '.0001?..', '.0111...', '..1.....', '........', '........']], (30, 125): [['.......!', '.....?!!', '....??!0', '....?100', '....1102', '....1322', '....332.', '....3...'], ['.......!', '.....!!!', '....?!?!', '....???0', '....?000', '....1010', '....111.', '....1...']], (30, 126): [['.......!', '.....?!!', '....??!.', '..00?...', '.001....', '.22113..', '..22133.', '......3.'], ['.......!', '.....!!!', '....?!!.', '..???...', '.0??....', '.00011..', '..00111.', '......1.']], (30, 127): [['.....!!.', '..??!!0.', '..1??00.', '..11.022', '...1322.', '...3344.', '...344..', '........'], ['.....!!.', '..???!!.', '..??!!!.', '..??.000', '...1100.', '...1100.', '...111..', '........']], (30, 186): [], (30, 187): [['......!.', '.....!!?', '.....!??', '....00?.', '...00112', '..331122', '...33.2.', '........'], ['......!.', '.....!!!', '.....?!!', '....???.', '...0??11', '..000111', '...00.1.', '........']], (30, 189): [['......!!', '.....!!.', '......??', '.....??.', '......00', '.....00.', '........', '........'], ['......!!', '.....!!.', '......!!', '.....??.', '......??', '.....??.', '........', '........']], (30, 191): [['......!!', '.....!!?', '......??', '...001?2', '.3001122', '33441.2.', '344.....', '........'], ['......!!', '.....!!!', '......!!', '...??000', '.1???000', '111??.0.', '111.....', '........']], (30, 239): [], (30, 247): [['......!!', '.....!!?', '....00??', '..1002?.', '.11322..', '.1332...', '..344...', '..44....'], ['......!!', '.....!!!', '....?!?!', '..00???.', '.000??..', '.0101...', '..111...', '..11....']], (30, 254): [], (30, 255): [['......!!', '.....!!?', '.....0??', '....00?.', '....011.', '....11..', '........', '........'], ['......!!', '.....!!!', '.....!!!', '....???.', '....???.', '....??..', '........', '........']], (30, 367): [], (30, 381): [], (30, 383): [], (30, 495): [], (30, 511): [], (31, 47): [['......!!', '.....!!!', '.....???', '.....??.', '........', '........', '........', '........'], ['......!!', '.....??!', '.....?!!', '.....??.', '........', '........', '........', '........']], (31, 63): [['......!!', '....?!!!', '....??00', '....??00', '...11220', '.3111222', '.33.....', '.33.....'], ['......!!', '....??!!', '....??!!', '....??00', '...11100', '.2211100', '.22.....', '.22.....']], (31, 79): [['.......!', '....??!!', '...???!!', '...00011', '...00111', '...22333', '...2233.', '...2....'], ['.......!', '....???!', '...0?!!!', '...0?111', '...00021', '...33321', '...3222.', '...3....']], (31, 94): [['.......!', '......!!', '...???!!', '..00??11', '..000111', '...22333', '...2233.', '...2....'], ['.......!', '......!!', '...??!!0', '..??1100', '..?11002', '...13322', '...3322.', '...3....']], (31, 95): [['.......!', '......!!', '.....?!!', '....0??.', '.1100??.', '.110022.', '.133222.', '.333....'], ['.......!', '......!!', '.....!!!', '....???.', '.000??1.', '.002?11.', '.022111.', '.222....']], (31, 111): [['......!!', '....??!!', '....???!', '....00..', '.111000.', '.1122...', '.33222..', '.333....'], ['......!!', '....???!', '....?!!!', '....??..', '.000111.', '.0221...', '.00211..', '.222....']], (31, 121): [['.......!', '.....?!!', '....??!!', '....??..', '.00111..', '.0011...', '.0......', '........'], ['.......!', '.....!!!', '....???!', '....0?..', '.1000?..', '.1110...', '.1......', '........']], (31, 122): [['.......!', '.....?!!', '....??!!', '..00??11', '.2000.11', '.2234441', '.223344.', '...33...'], ['.......!', '.....!!!', '....??!0', '..1??000', '.111?.02', '.1344222', '.333442.', '...34...']], (31, 123): [['.......!', '.....?!!', '....??!!', '....??00', '....1100', '....1110', '..222333', '...2233.'], ['.......!', '.....!!!', '....??!!', '....???0', '....?000', '....1200', '..111222', '...1122.']], (31, 124): [['.......!', '....??!!', '..0???!!', '..00111.', '.200311.', '22.433..', '224433..', '..44....'], ['.......!', '....?!!!', '..???!00', '..?1220.', '.111200.', '31.224..', '333444..', '..34....']], (31, 125): [['.......!', '.....?!!', '....??!!', '....??00', '111.2200', '.11222.0', '.333....', '..33....'], ['.......!', '.....!!!', '....?!?!', '....???0', '111.?000', '.12220.0', '.112....', '..22....']], (31, 126): [['.......!', '.....?!!', '....??!!', '..00??11', '..000111', '..222333', '..22.33.', '........'], ['.......!', '.....!!!', '....?!!0', '..???000', '..??1002', '..111222', '..11.22.', '........']], (31, 127): [['.......!', '.....?!!', '....??!!', '....??0.', '.112200.', '.1122003', '.1442.33', '..444.33'], ['.......!', '.....!!!', '....?!!!', '....???.', '.000???.', '.0001222', '.0111.22', '..111.22']], (31, 186): [['.....!..', '...??!!.', '..???!!.', '...00111', '...0011.', '....0...', '........', '........'], ['.....!..', '...?!!!.', '..???!0.', '...?1000', '...1110.', '....1...', '........', '........']], (31, 187): [['......!!', '.....!!!', '......?.', '......??', '...000??', '.122003.', '1122233.', '11...33.'], ['......!!', '.....!!!', '......!.', '......??', '...00???', '.10002?.', '1110222.', '11...22.']], (31, 189): [], (31, 191): [['......!!', '.....!!!', '......??', '...00???', '..000111', '..22211.', '.332244.', '.333444.'], ['......!!', '.....!!!', '......!!', '...??000', '..???000', '..1??20.', '.111222.', '.111222.']], (31, 239): [], (31, 247): [['......!!', '.....!!!', '....?000', '..1??00.', '.11??2..', '.11322.4', '..332244', '..33..44'], ['......!!', '.....!!!', '....?!?!', '..00???.', '.000??..', '.01012.2', '..111222', '..11..22']], (31, 254): [['......!!', '.....!!!', '.....??.', '...0???.', '..001222', '33001122', '334411..', '.3444...'], ['......!!', '.....!!!', '.....!!.', '...??00.', '..???000', '11??2200', '111222..', '.1122...']], (31, 255): [['......!!', '.....!!!', '.....???', '..0111??', '..001122', '33004222', '335544..', '355544..'], ['......!!', '.....!!!', '.....!!!', '..???000', '..???000', '11??2200', '111222..', '111222..']], (31, 367): [], (31, 381): [], (31, 383): [['.....!!!', '.....!!.', '..???000', '..??1100', '.2211133', '.2244333', '.244455.', '....555.'], ['.....!!!', '.....!!.', '..???!!!', '..???000', '.1?1?000', '.1112020', '.111222.', '....222.']], (31, 495): [], (31, 511): [], (47, 63): [], (47, 79): [['.....!!!', '.....!.!', '.....?.?', '.....???', '........', '........', '........', '........'], ['.....!!!', '.....!.?', '.....!.?', '.....???', '........', '........', '........', '........']], (47, 94): [['......!!', '...???!.', '..0?0?!!', '..000111', '..223131', '...2333.', '..22....', '........'], ['......!!', '...??!!.', '..??0!11', '..?00112', '..003122', '...3322.', '..33....', '........']], (47, 95): [], (47, 111): [['......!!', '.......!', '...???!!', '...?.?00', '...111.0', '...1.100', '.2.2.3.3', '.222.333'], ['......!!', '.......!', '...??!!!', '...?.000', '...???.0', '...1.200', '.1.1.2.2', '.111.222']], (47, 121): [['....!!??', '....!.?.', '.0.0!!??', '.000.111', '.22..1.1', '..2333..', '.223.3..', '........'], ['....!???', '....!.?.', '.0.!!!?1', '.000.111', '.02..3.1', '..2333..', '.222.3..', '........']], (47, 122): [['......!!', '....??!.', '...00?!!', '...0??11', '...00221', '...33211', '....322.', '...33...'], ['......!!', '....?!!.', '...???!0', '...?1000', '...11102', '...13222', '....332.', '...33...']], (47, 123): [], (47, 124): [['....!!!.', '..??!.!.', '..?...00', '..??...0', '...1.100', '...111..', '........', '........'], ['....!??.', '..!!!.?.', '..!...??', '..00...1', '...0.111', '...001..', '........', '........']], (47, 125): [['......!!', '......!.', '....??!!', '..00?...', '..0.??11', '..00..1.', '22233311', '2.23.3..'], ['......!!', '......!.', '....?!!!', '..???...', '..?.?000', '..12..0.', '11122200', '1.12.2..']], (47, 126): [['......!!', '.....??!', '.....?!!', '.....??.', '.....000', '.1112020', '3131222.', '333.....'], ['......!!', '.....!!!', '.....!??', '.....??.', '.....??0', '.1122000', '1122200.', '112.....']], (47, 127): [], (47, 186): [], (47, 187): [], (47, 189): [], (47, 191): [], (47, 239): [['....!!!.', '.??.!.!.', '.?.000..', '.??0.011', '.223.3.1', '.2.33311', '.22.4.4.', '....444.'], ['....!!!.', '.??.!.!.', '.?.?!!..', '.???.000', '.111.0.0', '.1.12200', '.11.2.2.', '....222.']], (47, 247): [['....!.!.', '.??.!!!.', '..?000..', '.??0.011', '.223.31.', '..233311', '.22.444.', '....4.4.'], ['....!.!.', '.??.!!!.', '..??!!..', '.???.000', '.111.00.', '..112200', '.11.222.', '....2.2.']], (47, 254): [], (47, 255): [], (47, 367): [['.....!!!', '.....!.!', '..???0.0', '11?.?000', '1.2223.3', '112.2333', '....4.4.', '....444.'], ['.....!!!', '.....!.!', '..???!.!', '000.?111', '0.???1.1', '000.2121', '....2.2.', '....222.']], (47, 381): [], (47, 383): [], (47, 495): [], (47, 511): [], (63, 79): [], (63, 94): [], (63, 95): [['.....!!!', '.....!!!', '.....???', '.....???', '........', '........', '........', '........'], ['.....!!!', '.....!!?', '.....!??', '.....???', '........', '........', '........', '........']], (63, 111): [['......!!', '....??!!', '....??!!', '....??..', '........', '........', '........', '........'], ['......!!', '....???!', '....?!!!', '....??..', '........', '........', '........', '........']], (63, 121): [], (63, 122): [], (63, 123): [['......!!', '....??!!', '....??!!', '....??..', '........', '........', '........', '........'], ['......!!', '....?!!!', '....???!', '....??..', '........', '........', '........', '........']], (63, 124): [], (63, 125): [], (63, 126): [['......!!', '....??!!', '..00??!!', '..00??11', '..002211', '..332211', '..3322..', '..33....'], ['......!!', '....?!!!', '..???!00', '..??1000', '..111022', '..113222', '..3332..', '..33....']], (63, 127): [['......!!', '......!!', '....??!!', '0011??22', '0011??22', '0011..22', '.333444.', '.333444.'], ['......!!', '......!!', '....?!!!', '00???111', '00???111', '0002..31', '.222333.', '.222333.']], (63, 186): [], (63, 187): [['.....!!.', '..???!!.', '..???!!.', '...00111', '...00111', '...00...', '........', '........'], ['.....!!.', '..??!!!.', '..???!0.', '...?1000', '...11100', '...11...', '........', '........']], (63, 189): [], (63, 191): [['......!!', '...???!!', '00.???!!', '00111...', '00111...', '2233344.', '2233344.', '22...44.'], ['......!!', '...??!!!', '00.???!!', '000??...', '00111...', '2211133.', '2221333.', '22...33.']], (63, 239): [], (63, 247): [], (63, 254): [], (63, 255): [['......!!', '..??00!!', '..??00!!', '..??00..', '....111.', '....111.', '........', '........'], ['......!!', '..???!!!', '..???!!!', '..??00..', '....000.', '....000.', '........', '........']], (63, 367): [], (63, 381): [], (63, 383): [], (63, 495): [], (63, 511): [['.....!!!', '.....!!!', '.....???', '.....???', '.....000', '.....000', '........', '........'], ['.....!!!', '.....!!!', '.....!!!', '.....???', '.....???', '.....???', '........', '........']], (79, 94): [['.......!', '....???!', '...0?!!!', '...0?111', '...00021', '...33321', '...3222.', '...3....'], ['.......!', '....??!!', '...??!!0', '...?1100', '...11002', '...13322', '...3322.', '...3....']], (79, 95): [], (79, 111): [['.......!', '...???.!', '...?.!!!', '000?1112', '0.3.1..2', '0.3.1222', '..333...', '........'], ['.......!', '...??!.!', '...?.!!!', '000???11', '0.0.2..1', '0.2.2111', '..222...', '........']], (79, 121): [['.......!', '....???!', '....?!!!', '....?...', '........', '........', '........', '........'], ['.......!', '....?!!!', '....???!', '....?...', '........', '........', '........', '........']], (79, 122): [['.......!', '....???!', '...0?!!!', '...0?111', '...00021', '...33321', '...3222.', '...3....'], ['.......!', '....?!!!', '...???!0', '...?1000', '...11102', '...13222', '...3332.', '...3....']], (79, 123): [], (79, 124): [['....!!!.', '..???.!.', '..?...!0', '..?1...0', '...1.000', '...111..', '........', '........'], ['....!??.', '..!!!.?.', '..!...??', '..00...1', '...0.111', '...001..', '........', '........']], (79, 125): [], (79, 126): [], (79, 127): [['.......!', '...?000!', '111?0!!!', '1???02..', '1.33324.', '..32224.', '..3.444.', '........'], ['.......!', '...??!!!', '000??!!!', '000???..', '0.11122.', '..11122.', '..1.222.', '........']], (79, 186): [], (79, 187): [], (79, 189): [], (79, 191): [], (79, 239): [], (79, 247): [], (79, 254): [], (79, 255): [], (79, 367): [['.....!!!', '.....?.!', '.000.?.!', '.0.???1.', '.0.22213', '.4.21113', '.4.2.333', '.444....'], ['.....!!!', '.....!.!', '.???.!.!', '.?.?000.', '.?.?0101', '.2.20101', '.2.2.111', '.222....']], (79, 381): [], (79, 383): [], (79, 495): [], (79, 511): [], (94, 95): [], (94, 111): [], (94, 121): [], (94, 122): [['.......!', '....??!!', '...??!!.', '...?....', '........', '........', '........', '........'], ['.......!', '....?!!!', '...???!.', '...?....', '........', '........', '........', '........']], (94, 123): [['......!.', '.....!!.', '.??0!!11', '??00.112', '?003.122', '...3322.', '....33..', '........'], ['......!.', '.....!!.', '.?000!!!', '??00.111', '???0.211', '...2221.', '....22..', '........']], (94, 124): [['....!!..', '...!!?..', '...!.??.', '..00..??', '...00.1.', '....011.', '....11..', '........'], ['....!!..', '...??!..', '...?.!!.', '..??..00', '...11.0.', '....100.', '....11..', '........']], (94, 125): [], (94, 126): [['......!!', '.....!!?', '.....!??', '.....??.', '.....00.', '.112003.', '1122033.', '122.33..'], ['......!!', '.....!!!', '.....!??', '.....??.', '.....??.', '.001122.', '0011122.', '001.22..']], (94, 127): [], (94, 186): [], (94, 187): [['......!.', '.....!!?', '....!!??', '...00??.', '..00122.', '..031122', '...33112', '....33..'], ['......!.', '.....!!!', '....??!!', '...0???.', '..000?1.', '..002111', '...22211', '....22..']], (94, 189): [], (94, 191): [], (94, 239): [], (94, 247): [['......!!', '..??.!!0', '.??11!00', '2?11300.', '221.33..', '.22..334', '......44', '.....44.'], ['......!!', '..??.!!!', '.???0!0!', '1?1?000.', '111.00..', '.11..222', '......22', '.....22.']], (94, 254): [['.....!!.', '....!!?.', '....!??0', '...1??00', '..11200.', '311224..', '332244..', '.3344...'], ['.....!!.', '....!!!.', '....!!??', '...00???', '..000??.', '110022..', '111222..', '.1122...']], (94, 255): [], (94, 367): [], (94, 381): [], (94, 383): [], (94, 495): [], (94, 511): [], (95, 111): [['.....!!!', '.....!!?', '.....!??', '.....???', '........', '........', '........', '........'], ['.....!!!', '.....!??', '.....!!?', '.....???', '........', '........', '........', '........']], (95, 121): [], (95, 122): [], (95, 123): [['.......!', '...???!!', '...??!!!', '...?....', '........', '........', '........', '........'], ['.......!', '...??!!!', '...???!!', '...?....', '........', '........', '........', '........']], (95, 124): [], (95, 125): [['....!!!.', '..?.!!..', '..??!000', '..???100', '....11.0', '...111..', '........', '........'], ['....!!!.', '..?.?!..', '..???!!0', '..?11000', '....10.0', '...111..', '........', '........']], (95, 126): [['.......!', '...???!!', '...??!!!', '000?.111', '002..11.', '022.31..', '22233...', '..333...'], ['.......!', '...??!!!', '...??!!0', '11??.000', '111..00.', '221.33..', '22233...', '..233...']], (95, 127): [['.....!!!', '..???0!!', '..??00.!', '..?000..', '111.2223', '114.2233', '1.442333', '..444...'], ['.....!!!', '..???!!!', '..??00.!', '..??00..', '111.0002', '111.3222', '1.333222', '..333...']], (95, 186): [], (95, 187): [['.....!..', '....?!!.', '...??!!!', '..???000', '..11100.', '...110..', '....1...', '........'], ['.....!..', '....!!!.', '...?!!00', '..???000', '..??110.', '...111..', '....1...', '........']], (95, 189): [['.....!..', '....?!!.', '...??!!!', '..???000', '..11100.', '...110..', '....1...', '........'], ['.....!..', '....!!!.', '...?!0!0', '..???000', '..?1?10.', '...111..', '....1...', '........']], (95, 191): [], (95, 239): [], (95, 247): [], (95, 254): [], (95, 255): [], (95, 367): [], (95, 381): [], (95, 383): [], (95, 495): [], (95, 511): [], (111, 121): [], (111, 122): [], (111, 123): [['......!!', '....???!', '....?!!!', '....??..', '........', '........', '........', '........'], ['......!!', '....?!!!', '....???!', '....??..', '........', '........', '........', '........']], (111, 124): [], (111, 125): [['.....!!.', '.....!..', '....?!!!', '..?.?000', '..???0.0', '..1110..', '....1...', '...11...'], ['.....!!.', '.....!..', '....!!!?', '..0.0???', '..000?.?', '..0111..', '....1...', '...11...']], (111, 126): [['.....!!.', '..???!..', '.0?.?!!!', '.0?0.111', '.000.121', '.333212.', '...3222.', '..33....'], ['.....!!.', '..??!!..', '.??.!!00', '.??1.000', '.111.022', '.113322.', '...3322.', '..33....']], (111, 127): [], (111, 186): [], (111, 187): [], (111, 189): [['....!!..', '...?!...', '.?.?!!!.', '.???.000', '..1110.0', '....10..', '...11...', '........'], ['....!!..', '...!!...', '.?.?!!0.', '.???.000', '..?110.0', '....11..', '...11...', '........']], (111, 191): [], (111, 239): [], (111, 247): [], (111, 254): [], (111, 255): [['......!!', '..??000!', '111?0!!!', '1???0022', '11334442', '55534222', '533344..', '55......'], ['......!!', '..???!!!', '00???!!!', '000??111', '00022111', '33322211', '333222..', '33......']], (111, 367): [], (111, 381): [], (111, 383): [], (111, 495): [['.....!!!', '..???!.!', '..?.000!', '..??0...', '....001.', '....1.1.', '....111.', '........'], ['.....!!!', '..???!.!', '..?.?!!!', '..???...', '....000.', '....0.0.', '....000.', '........']], (111, 511): [], (121, 122): [['.......!', '....?!!!', '...0???!', '...0?111', '..000.1.', '.222.31.', '..2333..', '..2..3..'], ['.......!', '....?!!!', '...???!0', '...?1000', '..111.0.', '.221.33.', '..2233..', '..2..3..']], (121, 123): [['.......!', '.....!!!', '...?..0!', '...?000.', '.1???20.', '.1113222', '.1..32..', '...333..'], ['.......!', '.....!!!', '...?..!!', '...???0.', '.11??00.', '.1112000', '.1..22..', '...222..']], (121, 124): [['.......!', '.....!!!', '.....?.!', '.....???', '.....?..', '........', '........', '........'], ['.......!', '.....!!!', '.....!.?', '.....???', '.....?..', '........', '........', '........']], (121, 125): [['.......!', '..?..!!!', '..???0.!', '.1?0002.', '.111302.', '.1..3222', '...333..', '........'], ['.......!', '..?..!!!', '..???!.!', '.0?0?11.', '.000221.', '.0..2111', '...222..', '........']], (121, 126): [], (121, 127): [['.......!', '...?0!!!', '1???000!', '111?02..', '1.32224.', '..33324.', '..3..444', '........'], ['.......!', '...??!!!', '000??!!!', '000???..', '0.11122.', '..11122.', '..1..222', '........']], (121, 186): [['.....!..', '...!!!?.', '..000!?.', '...01???', '...0111.', '....1...', '........', '........'], ['.....!..', '...?!!!.', '..???!0.', '...?1000', '...1110.', '....1...', '........', '........']], (121, 187): [], (121, 189): [], (121, 191): [], (121, 239): [], (121, 247): [], (121, 254): [], (121, 255): [], (121, 367): [], (121, 381): [], (121, 383): [], (121, 495): [], (121, 511): [], (122, 123): [['.......!', '.....!!!', '......!?', '..0..???', '000..1?.', '.023111.', '.223331.', '..223...'], ['.......!', '.....!!!', '......!!', '..?..000', '???..00.', '.??1220.', '.111222.', '..112...']], (122, 124): [['.......!', '.....!!!', '.....?!.', '....???.', '....?...', '........', '........', '........'], ['.......!', '.....!!!', '.....!?.', '....???.', '....?...', '........', '........', '........']], (122, 125): [['......!!', '...??!!.', '....??!0', '...1?000', '..111.0.', '...21.33', '..22233.', '....2.3.'], ['......!!', '...???!.', '....?!!!', '...??000', '..111.0.', '...12.00', '..11222.', '....2.2.']], (122, 126): [['.......!', '.....!!!', '.....?!.', '....???0', '...1?000', '.211130.', '222.133.', '2...33..'], ['.......!', '.....!!!', '.....!!.', '....??00', '...??000', '.11??02.', '111.222.', '1...22..']], (122, 127): [], (122, 186): [['......!.', '.....!!!', '.....!?.', '....???.', '.....?..', '........', '........', '........'], ['......!.', '.....!!!', '.....?!.', '....???.', '.....?..', '........', '........', '........']], (122, 187): [['......!.', '.....!!!', '...?.!0.', '..???00.', '..?12200', '.311122.', '.33312..', '..3.....'], ['......!.', '.....!!!', '...?.!!.', '..???00.', '..??1000', '.221110.', '.22211..', '..2.....']], (122, 189): [['......!.', '...?.!!!', '..???0.!', '..?.00..', '.1..200.', '1113222.', '1.3332..', '....3...'], ['......!.', '...?.!!!', '..???!.!', '..?.?0..', '.1..000.', '1112020.', '1.1222..', '....2...']], (122, 191): [['......!.', '.....!!!', '..?..!00', '.???100.', '.?21110.', '322241..', '333244..', '.3.44...'], ['......!.', '.....!!!', '..?..!!!', '.???000.', '.???000.', '111220..', '111222..', '.1.22...']], (122, 239): [], (122, 247): [['.....!!.', '....!!..', '..?00!1.', '..??0011', '.??2011.', '.2223344', '..23344.', '....3.4.'], ['.....!!.', '....!!..', '..??!!!.', '..???000', '.1?1?00.', '.1112200', '..11222.', '....2.2.']], (122, 254): [], (122, 255): [], (122, 367): [], (122, 381): [], (122, 383): [], (122, 495): [], (122, 511): [], (123, 124): [], (123, 125): [['.......!', '.....!!!', '....??!!', '....???.', '....?...', '........', '........', '........'], ['.......!', '.....!!!', '....?!?!', '....???.', '....?...', '........', '........', '........']], (123, 126): [['.......!', '.....!!!', '.....?!!', '.....???', '.....??.', '........', '........', '........'], ['.......!', '.....!!!', '.....!!?', '.....???', '.....??.', '........', '........', '........']], (123, 127): [['.......!', '.....!!!', '..??00!!', '1???0002', '111?0222', '1133.422', '.333.44.', '...3444.'], ['.......!', '.....!!!', '..???!!!', '000??111', '000??111', '0222.331', '.222.33.', '...2333.']], (123, 186): [], (123, 187): [['......!.', '...???!!', '...??!!!', '....?...', '........', '........', '........', '........'], ['......!.', '...??!!!', '...???!!', '....?...', '........', '........', '........', '........']], (123, 189): [['.....!..', '..?!!!0.', '.??.!!00', '.???.000', '111..22.', '1133222.', '.1333.2.', '..3.....'], ['.....!..', '..??!!!.', '.??.!0!0', '.1??.000', '111..20.', '1313222.', '.3332.2.', '..3.....']], (123, 191): [['.....!!!', '..?000!!', '..??00!.', '.???011.', '.222111.', '.223..14', '..233444', '..333.44'], ['.....!!!', '..???!!!', '..???0!.', '.11?000.', '.111000.', '.112..33', '..222333', '..222.33']], (123, 239): [], (123, 247): [['.....!!!', '...??!!.', '...???!0', '11.?.000', '111..200', '13334222', '.334422.', '..3444..'], ['.....!!!', '...??!!.', '...???!!', '00.?.?11', '000..111', '02023131', '.222333.', '..2233..']], (123, 254): [], (123, 255): [['......!!', '.....!!!', '.....??!', '....???.', '....00?.', '...1000.', '..110...', '..111...'], ['......!!', '.....!!!', '.....!!!', '....???.', '....???.', '...00??.', '..000...', '..000...']], (123, 367): [], (123, 381): [], (123, 383): [], (123, 495): [], (123, 511): [], (124, 125): [['.......!', '.....!!!', '.....!??', '...011?.', '.0001??2', '.0311222', '..3332..', '....3...'], ['.......!', '.....!!!', '.....!?!', '...0???.', '.000?1?1', '.0202111', '..2221..', '....2...']], (124, 126): [['......!.', '....!!!.', '....!?00', '...???0.', '...?100.', '221113..', '.21333..', '.223....'], ['......!.', '....!!!.', '....!!??', '...00??.', '...00??.', '110022..', '.11222..', '.112....']], (124, 127): [['.......!', '.....!!!', '...??!00', '.11?220.', '.1??200.', '113224..', '333444..', '3..4....'], ['.......!', '.....!!!', '...?0!!!', '.???000.', '.???000.', '111222..', '111222..', '1..2....']], (124, 186): [], (124, 187): [['......!.', '....!!!?', '...0!???', '.0001?..', '.011122.', '..1.332.', '.....322', '.....33.'], ['......!.', '....?!!!', '...???!!', '.00??1..', '.000111.', '..0.112.', '.....222', '.....22.']], (124, 189): [], (124, 191): [], (124, 239): [], (124, 247): [], (124, 254): [], (124, 255): [], (124, 367): [], (124, 381): [], (124, 383): [], (124, 495): [], (124, 511): [], (125, 126): [['......!.', '....!!!.', '....!?!?', '.....???', '.....?..', '........', '........', '........'], ['......!.', '....!!!.', '....!!??', '.....???', '.....?..', '........', '........', '........']], (125, 127): [], (125, 186): [], (125, 187): [['.....!!.', '...???!.', '..00?!!!', '..0??111', '.000221.', '.333211.', '..3222..', '..33....'], ['.....!!.', '...?!!!.', '..???!00', '..1??000', '.111220.', '.113222.', '..3332..', '..33....']], (125, 189): [['......!!', '...???!.', '....?!!!', '...??...', '........', '........', '........', '........'], ['......!!', '...??!!.', '....??!!', '...??...', '........', '........', '........', '........']], (125, 191): [], (125, 239): [], (125, 247): [['.....!.!', '.?.?.!!!', '.???000!', '.?1110..', '2221.003', '.2114333', '224443.3', '..4.4...'], ['.....!.!', '.?.?.!!!', '.???00!!', '.??000..', '1110.022', '.1133222', '113332.2', '..3.3...']], (125, 254): [], (125, 255): [], (125, 367): [], (125, 381): [], (125, 383): [], (125, 495): [], (125, 511): [], (126, 127): [['......!!', '..?00!!!', '???00!11', '??220011', '..222113', '..442333', '..44433.', '....4...'], ['......!!', '..?000!!', '???00!!!', '???00111', '..222111', '..223331', '..22333.', '....3...']], (126, 186): [], (126, 187): [['......!!', '.....!!!', '.....!?.', '....???.', '....??..', '........', '........', '........'], ['......!!', '.....!!!', '.....?!.', '....???.', '....??..', '........', '........', '........']], (126, 189): [['....!!..', '...!!...', '.?.!!00.', '.???.000', '..??11.0', '....11..', '...11...', '........'], ['....!!..', '...!!...', '.?.?!!0.', '.???.000', '..?110.0', '....11..', '...11...', '........']], (126, 191): [['......!!', '....??!!', '00.??!!1', '000??111', '220..113', '.2244333', '.224433.', '....44..'], ['......!!', '....?!!!', '00.???!!', '000???11', '002..111', '.2223311', '.222333.', '....33..']], (126, 239): [], (126, 247): [['......!!', '.??..!!!', '.??00!11', '??00011.', '220..11.', '222.3344', '..233.44', '...3344.'], ['......!!', '.??..!!!', '.???0!0!', '1?1?000.', '111..00.', '112.2333', '..222.33', '...2233.']], (126, 254): [['......!!', '.....!!!', '.??..!0.', '??11000.', '??110022', '33411222', '334442..', '.3344...'], ['......!!', '.....!!!', '.??..!!.', '???0011.', '??000111', '22003311', '222333..', '.2233...']], (126, 255): [['......!!', '.....!!!', '.....!??', '.....???', '.....?00', '...11000', '...110..', '....11..'], ['......!!', '.....!!!', '.....!!!', '.....???', '.....???', '...000??', '...000..', '....00..']], (126, 367): [], (126, 381): [], (126, 383): [], (126, 495): [], (126, 511): [], (127, 186): [], (127, 187): [], (127, 189): [], (127, 191): [['......!!', '...???!!', '...??!!!', '...??...', '........', '........', '........', '........'], ['......!!', '...??!!!', '...???!!', '...??...', '........', '........', '........', '........']], (127, 239): [], (127, 247): [['.....!!!', '.....!!.', '...??!!0', '...??000', '..???000', '.111222.', '.11122..', '...122..'], ['.....!!!', '.....!!.', '...???!!', '...??000', '..11??00', '.112200.', '.11122..', '...222..']], (127, 254): [['....!!..', '...?!!..', '.???!!!.', '.???.000', '..111000', '...110..', '...11...', '........'], ['....!!..', '...!!!..', '.??!!00.', '.???.000', '..??1100', '...111..', '...11...', '........']], (127, 255): [], (127, 367): [['.....!!!', '....?!!!', '....???!', '....???.', '........', '........', '........', '........'], ['.....!!!', '....?!?!', '....?!?!', '....???.', '........', '........', '........', '........']], (127, 381): [], (127, 383): [], (127, 495): [], (127, 511): [], (186, 187): [], (186, 189): [], (186, 191): [], (186, 239): [], (186, 247): [], (186, 254): [], (186, 255): [], (186, 367): [], (186, 381): [], (186, 383): [], (186, 495): [], (186, 511): [], (187, 189): [['......!.', '.....!!!', '....??!!', '....???.', '.....?..', '........', '........', '........'], ['......!.', '.....!!!', '....?!?!', '....???.', '.....?..', '........', '........', '........']], (187, 191): [], (187, 239): [], (187, 247): [], (187, 254): [], (187, 255): [], (187, 367): [], (187, 381): [], (187, 383): [], (187, 495): [], (187, 511): [], (189, 191): [], (189, 239): [], (189, 247): [], (189, 254): [], (189, 255): [], (189, 367): [], (189, 381): [], (189, 383): [], (189, 495): [], (189, 511): [], (191, 239): [], (191, 247): [['......!!', '.....!!!', '....??!!', '....???.', '....??..', '........', '........', '........'], ['......!!', '.....!!!', '....?!?!', '....???.', '....??..', '........', '........', '........']], (191, 254): [['....!!..', '...!!!..', '.???!!0.', '.???.000', '..?11000', '...111..', '...11...', '........'], ['....!!..', '...!!!..', '.??!!00.', '.???.000', '..??1100', '...111..', '...11...', '........']], (191, 255): [], (191, 367): [], (191, 381): [], (191, 383): [], (191, 495): [], (191, 511): [], (239, 247): [], (239, 254): [], (239, 255): [], (239, 367): [['.....!!!', '.....!.!', '....??!!', '....?.?.', '....???.', '........', '........', '........'], ['.....!!!', '.....!.!', '....?!?!', '....?.?.', '....???.', '........', '........', '........']], (239, 381): [], (239, 383): [], (239, 495): [], (239, 511): [], (247, 254): [['.....!!.', '.....!!!', '....?!?!', '....???.', '.....??.', '........', '........', '........'], ['.....!!.', '.....!!!', '....??!!', '....???.', '.....??.', '........', '........', '........']], (247, 255): [], (247, 367): [], (247, 381): [['.....!!!', '...??!!.', '....??!!', '...???..', '........', '........', '........', '........'], ['.....!!!', '...???!.', '....?!!!', '...???..', '........', '........', '........', '........']], (247, 383): [], (247, 495): [], (247, 511): [], (254, 255): [], (254, 367): [], (254, 381): [], (254, 383): [], (254, 495): [], (254, 511): [], (255, 367): [], (255, 381): [], (255, 383): [['.....!!!', '.....!!!', '....??!!', '....???.', '....???.', '........', '........', '........'], ['.....!!!', '.....!!!', '....?!?!', '....???.', '....???.', '........', '........', '........']], (255, 495): [], (255, 511): [], (367, 381): [], (367, 383): [], (367, 495): [], (367, 511): [], (381, 383): [], (381, 495): [], (381, 511): [], (383, 495): [], (383, 511): [], (495, 511): []}
for case in xrange(input()):
if case: raw_input() # skip empty line
print 'Case #%d: %s' % (case+1, two_tiling())