#NOTE: Use FOUR SPACES (Dont USE TABS) for indentation
x, y = [1, 0], [0, 1]
def isValid(i, j):
return i >= 0 and i < r and j >= 0 and j < c and visited[i][j] == 0
def dfs(i, j, path):
visited[i][j] = 1
if i == r - 1 and j == c - 1:
ans.append(path)
for dir_ in range(2):
temp_i, temp_j = i + x[dir_], j + y[dir_]
if isValid(temp_i, temp_j):
dfs(temp_i, temp_j, path + str(mat[temp_i][temp_j]))
visited[i][j] = 0
if __name__ == "__main__":
t = int(input().strip())
for ti in range(t):
ans = []
rc = input().strip().split(' ')
r = int(rc[0])
c = int(rc[1])
visited = [[0] * c for _ in range(r)]
mat = [] # Empty List of Lists
for ri in range(r):
rowList = list(map(int, input().strip().split(' ')))
mat.append(rowList)
dfs(0, 0, "1")
for i in ans:
print(*i)
print()
I05PVEU6ICBVc2UgRk9VUiBTUEFDRVMgKERvbnQgVVNFIFRBQlMpIGZvciBpbmRlbnRhdGlvbgoKeCwgeSAgPSBbMSwgMF0sIFswLCAxXQoKZGVmIGlzVmFsaWQoaSwgaik6CiAgICByZXR1cm4gaSA+PSAwIGFuZCBpIDwgciBhbmQgaiA+PSAwIGFuZCBqIDwgYyBhbmQgdmlzaXRlZFtpXVtqXSA9PSAwCgpkZWYgZGZzKGksIGosIHBhdGgpOgogICAgdmlzaXRlZFtpXVtqXSA9IDEKICAgIGlmIGkgPT0gciAtIDEgYW5kIGogPT0gYyAtIDE6CiAgICAgICAgYW5zLmFwcGVuZChwYXRoKQogICAgZm9yIGRpcl8gaW4gcmFuZ2UoMik6CiAgICAgICAgdGVtcF9pLCB0ZW1wX2ogPSBpICsgeFtkaXJfXSwgaiArIHlbZGlyX10KICAgICAgICBpZiBpc1ZhbGlkKHRlbXBfaSwgdGVtcF9qKToKICAgICAgICAgICAgZGZzKHRlbXBfaSwgdGVtcF9qLCBwYXRoICsgc3RyKG1hdFt0ZW1wX2ldW3RlbXBfal0pKQogICAgdmlzaXRlZFtpXVtqXSA9IDAKICAgIAppZiAgX19uYW1lX18gPT0gIl9fbWFpbl9fIjoKICAgIHQgPSBpbnQoaW5wdXQoKS5zdHJpcCgpKQogICAgZm9yIHRpIGluIHJhbmdlKHQpOgogICAgICAgIGFucyA9IFtdCiAgICAgICAgcmMgPSBpbnB1dCgpLnN0cmlwKCkuc3BsaXQoJyAnKQogICAgICAgIHIgPSBpbnQocmNbMF0pICAKICAgICAgICBjID0gaW50KHJjWzFdKQogICAgICAgIHZpc2l0ZWQgPSBbWzBdICogYyBmb3IgXyBpbiByYW5nZShyKV0KICAgICAgICBtYXQgPSBbXSAgIyBFbXB0eSBMaXN0IG9mIExpc3RzICAKICAgICAgICBmb3IgcmkgaW4gcmFuZ2Uocik6CiAgICAgICAgICAgIHJvd0xpc3QgPSBsaXN0KG1hcChpbnQsIGlucHV0KCkuc3RyaXAoKS5zcGxpdCgnICcpKSkKICAgICAgICAgICAgbWF0LmFwcGVuZChyb3dMaXN0KQogICAgICAgIGRmcygwLCAwLCAiMSIpCiAgICAgICAgZm9yIGkgaW4gYW5zOgogICAgICAgICAgICBwcmludCgqaSkKICAgICAgICBwcmludCgp