def DFS(start):
    global sub_result, result, final_result

    if len(sub_result) == N-1:
        for i, j in sub_result:
            result += Battery[i][j]

        result += Battery[start][0]
        final_result.append(result)
        result = 0
        return

    for next in range(1, N):
        if not visited[next]:
            sub_result.append((start, next))
            visited[next] = True
            DFS(next)
            sub_result.remove((start, next))
            visited[next] = False


TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    Battery = [list(map(int, input().split())) for _ in range(N)]
    visited = [0] * N
    sub_result =  []
    result = 0
    final_result =[]
    DFS(0)

    print('#%d %d'%(tc, min(final_result)))

def IsSafe(y,x):
    return 0<=y<N and 0<=x<N

def DFS(y,x):
    global sub_result, result

    if result < sub_result:
        return

    if y == N-1 and x == N-1:
        result = sub_result
        return

    for dir in range(2):
        New_Y = y + dy[dir]
        New_X = x + dx[dir]
        if IsSafe(New_Y, New_X) and (New_Y, New_X) not in visited:
            visited.append((New_Y, New_X))
            sub_result += Data[New_Y][New_X]
            DFS(New_Y, New_X)
            visited.remove((New_Y, New_X))
            sub_result -= Data[New_Y][New_X]


TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    Data = [list(map(int, input().split())) for _ in range(N)]

    visited = []

    #우 하
    dy = [0, 1]
    dx = [1, 0]

    sub_result, result = Data[0][0], 987654321
    DFS(0,0)
    print('#%d %d'%(tc, result))

TC = int(input())
for tc in range(1, TC+1):
    bi_num = input()
    tri_num = input()

    bi_num_lst = []
    tri_num_lst = []
    for i in range(len(bi_num)):
        bi_num2 = list(bi_num)
        if bi_num2[i] == '0':
            bi_num2[i] = '1'
            bi_num_lst.append(int(''.join(bi_num2), 2))

        else:
            bi_num2[i] = '0'
            bi_num_lst.append(int(''.join(bi_num2), 2))


    for i in range(len(tri_num)):
        tri_num2 = list(tri_num)
        if tri_num2[i] == '0':
            tri_num2[i] = '1'
            tri_num_lst.append(int(''.join(tri_num2),3))
            tri_num2[i] = '0'
            tri_num2[i] = '2'
            tri_num_lst.append(int(''.join(tri_num2),3))

        elif tri_num2[i] == '1':
            tri_num2[i] = '2'
            tri_num_lst.append(int(''.join(tri_num2),3))
            tri_num2[i] = '1'
            tri_num2[i] = '0'
            tri_num_lst.append(int(''.join(tri_num2),3))

        else:
            tri_num2[i] = '0'
            tri_num_lst.append(int(''.join(tri_num2),3))
            tri_num2[i] = '2'
            tri_num2[i] = '1'
            tri_num_lst.append(int(''.join(tri_num2),3))

    result = 0
    for i in bi_num_lst:
        if i in tri_num_lst:
            result = i
            break

    print('#%d %d' % (tc, result))

Conversion = {'0':'0000', '1':'0001', '2':'0010', '3':'0011',
         '4':'0100', '5':'0101', '6':'0110', '7':'0111',
         '8':'1000', '9':'1001', 'A':'1010', 'B':'1011',
         'C':'1100', 'D':'1101', 'E':'1110', 'F':'1111'}

decryption = {'211':0, '221':1, '122':2, '411':3, '132':4, '231':5, '114':6, '312':7, '213':8, '112':9}

def reduce(c, b, a):
    min_num = min(c,b,a)
    c //= min_num
    b //= min_num
    a //= min_num
    return str(c)+str(b)+str(a)

TC = int(input())
for tc in range(1, TC+1):
    N, M = map(int, input().split())
    Scannner = [input() for _ in range(N)]

    Binary_lst = [''] * N
    for i in range(N):
        for j in range(M):
            Binary_lst[i] += Conversion[Scannner[i][j]]
    # print(Binary_lst)

    result = []
    visited = []
    ans = 0
    for y in range(N):
        a = b = c = 0
        for x in range(M*4-1, -1, -1):
            if b == 0 and c == 0 and Binary_lst[y][x] == '1':
                a += 1
            elif a > 0 and c == 0 and Binary_lst[y][x] == '0':
                b += 1
            elif a > 0 and b > 0 and Binary_lst[y][x] == '1':
                c += 1

            if a > 0 and b > 0 and c > 0 and Binary_lst[y][x] == '0':
                result.append(decryption[reduce(c, b, a)])
                a = b = c = 0

            if len(result) == 8:
                result = result[::-1]
                value = (result[0] + result[2] + result[4] + result[6]) * 3 + \
                        (result[1] + result[3] + result[5]) + result[7]

                if value % 10 == 0 and result not in visited:
                    ans += sum(result)

                visited.append(result)
                result = []

    print('#%d %d'%(tc, ans))