import sys
from collections import deque

sys.stdin=open("input2.txt", "r")

dirs = ([], [0,1],[0,-1],[-1,0],[1,0])

if __name__=="__main__":

    T=int(input())

    for tc in range(1,T+1):
        R,C,K = map(int, input().split())

        board = []
        heat = []
        check_board=[]
        walls = [[0]*C for _ in range(R)]
        heat_board = [[0]*C for _ in range(R)]

        for i in range(R):
            A = list(map(int, input().split()))
            for j in range(C):
                if A[j]!=0 and A[j]!=5:
                    heat.append([i,j])
                elif A[j]==5:
                    check_board.append([i,j])
            board+=[A]

        W = int(input())

        for _ in range(W):
            r,c,t = map(int, input().split())
            if t==0:
                walls[r-2][c-1]+=2**4
                walls[r-1][c-1]+=2**3
            elif t==1:
                walls[r-1][c-1]+=2**1
                walls[r-1][c]+=2**2

        # print(*board, sep='\n')
        # print()
        # print(*walls, sep='\n')

        cnt =0
        for _ in range(100):

            for h in heat:
                tmp=5
                d = board[h[0]][h[1]]

                heat_board[h[0]+dirs[d][0]][h[1]+dirs[d][1]]+=tmp
                tmp-=1
                
                q= deque([[h[0]+dirs[d][0], h[1]+dirs[d][1]]])
                
                visited = [[0]*C for _ in range(R)]

                while tmp:
                    for _ in range(len(q)):
                        pos = q.popleft()
                        next_check=[[pos[0],pos[1]]]
                        if d ==1:
                            if not (walls[pos[0]][pos[1]]&2**3):
                                next_check.append([pos[0]+dirs[3][0], pos[1]+dirs[3][1]])
                            if not (walls[pos[0]][pos[1]]&2**4):
                                next_check.append([pos[0]+dirs[4][0], pos[1]+dirs[4][1]])
                            
                            for pos in next_check:
                                nPos = [pos[0]+dirs[1][0], pos[1]+dirs[1][1]]
                                if 0<=nPos[0]<R and 0<=nPos[1]<C and not(walls[pos[0]][pos[1]]&2**1) and visited[nPos[0]][nPos[1]]==0:
                                    visited[nPos[0]][nPos[1]]=1
                                    heat_board[nPos[0]][nPos[1]]+=tmp
                                    q.append([nPos[0], nPos[1]])
                        elif d==2:
                            if not (walls[pos[0]][pos[1]]&2**3):
                                next_check.append([pos[0]+dirs[3][0], pos[1]+dirs[3][1]])
                            if not (walls[pos[0]][pos[1]]&2**4):
                                next_check.append([pos[0]+dirs[4][0], pos[1]+dirs[4][1]])
                            
                            for pos in next_check:
                                nPos = [pos[0]+dirs[2][0], pos[1]+dirs[2][1]]
                                if 0<=nPos[0]<R and 0<=nPos[1]<C and not(walls[pos[0]][pos[1]]&2**2) and visited[nPos[0]][nPos[1]]==0:
                                    visited[nPos[0]][nPos[1]]=1
                                    heat_board[nPos[0]][nPos[1]]+=tmp
                                    q.append([nPos[0], nPos[1]])
                        elif d==3:
                            if not (walls[pos[0]][pos[1]]&2**1):
                                next_check.append([pos[0]+dirs[1][0], pos[1]+dirs[1][1]])
                            if not (walls[pos[0]][pos[1]]&2**2):
                                next_check.append([pos[0]+dirs[2][0], pos[1]+dirs[2][1]])
                            
                            for pos in next_check:
                                nPos = [pos[0]+dirs[3][0], pos[1]+dirs[3][1]]
                                if 0<=nPos[0]<R and 0<=nPos[1]<C and not(walls[pos[0]][pos[1]]&2**3) and visited[nPos[0]][nPos[1]]==0:
                                    visited[nPos[0]][nPos[1]]=1
                                    heat_board[nPos[0]][nPos[1]]+=tmp
                                    q.append([nPos[0], nPos[1]])
                        elif d==4:
                            if not (walls[pos[0]][pos[1]]&2**1):
                                next_check.append([pos[0]+dirs[1][0], pos[1]+dirs[1][1]])
                            if not (walls[pos[0]][pos[1]]&2**2):
                                next_check.append([pos[0]+dirs[2][0], pos[1]+dirs[2][1]])
                            
                            for pos in next_check:
                                nPos = [pos[0]+dirs[4][0], pos[1]+dirs[4][1]]
                                if 0<=nPos[0]<R and 0<=nPos[1]<C and not(walls[pos[0]][pos[1]]&2**4) and visited[nPos[0]][nPos[1]]==0:
                                    visited[nPos[0]][nPos[1]]=1
                                    heat_board[nPos[0]][nPos[1]]+=tmp
                                    q.append([nPos[0], nPos[1]])
                    tmp-=1
            # print()
            # print(*heat_board, sep='\n')
            
            tmp_board = [[0]*C for _ in range(R)]

            for i in range(R):
                for j in range(C):
                    pos = [i,j]
                    cntTmp=0
                    for d in range(1,5):
                        
                        nPos = [pos[0]+dirs[d][0], pos[1]+dirs[d][1]]
                        if 0<=nPos[0]<R and 0<=nPos[1]<C and not (walls[pos[0]][pos[1]]&2**d):
                            if heat_board[pos[0]][pos[1]]>heat_board[nPos[0]][nPos[1]]:
                                cntTmp-=(heat_board[pos[0]][pos[1]]-heat_board[nPos[0]][nPos[1]])//4
                            else:
                                cntTmp+=(heat_board[nPos[0]][nPos[1]]-heat_board[pos[0]][pos[1]])//4
                    tmp_board[i][j] = cntTmp
            
            for i in range(R):
                for j in range(C):
                    heat_board[i][j]+=tmp_board[i][j]

            for i in range(R):
                if heat_board[i][0]:
                    heat_board[i][0]-=1
                
                if heat_board[i][C-1]:
                    heat_board[i][C-1]-=1

            for j in range(1,C-1):
                if heat_board[0][j]:
                    heat_board[0][j]-=1
                
                if heat_board[R-1][j]:
                    heat_board[R-1][j]-=1
            cnt+=1

            for check in check_board:
                if heat_board[check[0]][check[1]]<K:
                    break
            else:
                break
        else:
            cnt=101
                
        print(f'#{tc} {cnt}')

#1 1
#2 2
#3 3
#4 53
#5 101
#6 93
#7 35
#8 101
#9 94



_____________________________________________________________________________________________________________________________________

import sys

sys.stdin=open("input.txt", "r")

dirs = ([-1,0],[0,-1],[1,0],[0,1])

def deepcopy(arr):
    return [[cols for cols in rows] for rows in arr]

def dfs(high,visited, pos, cnt, flag):
    global ans, K
    # if h == []:
    #     ans = max(ans, cnt)
    #     return
    for d in dirs:
        nPos = [pos[0]+d[0], pos[1]+d[1]]
        if 0<=nPos[0]<N and 0<=nPos[1]<N and visited[nPos[0]][nPos[1]]==0:
            if board[nPos[0]][nPos[1]]<high:
                visited[pos[0]][pos[1]]=1
                dfs(board[nPos[0]][nPos[1]],deepcopy(visited), nPos,cnt+1,flag)
                visited[pos[0]][pos[1]]=0
            elif board[nPos[0]][nPos[1]]-K<high and flag==0:
                visited[pos[0]][pos[1]]=1
                dfs(high-1,deepcopy(visited), nPos,cnt+1,1)
                visited[pos[0]][pos[1]]=0
        ans = max(ans, cnt+1)

if __name__ == "__main__":
    T = int(input())
    for tc in range(1,T+1):

        N, K = map(int, input().split())
        highest=0
        hList =[]
        board = []
        for i in range(N):
            A = list(map(int, input().split()))
            for j in range(N):
                if A[j] > highest:
                    highest = A[j]
                    hList=[[i,j]]
                elif A[j]==highest:
                    hList.append([i,j])
            board+=[A]
        # print(*board, sep='\n')
        # print(hList)
        ans =0
        for h in hList:
            visited = [[0]*N for _ in range(N)]
            dfs(highest,visited, h, 0, 0)
        print(f'#{tc} {ans}')
#1 6
#2 3
#3 7
#4 4
#5 2
#6 12
#7 6
#8 7
#9 10
#10 19

 

______________________________________________________________________________________________________________________________________________


import sys
from collections import deque


sys.stdin = open("input.txt", "r")

dirs = ([-1,0],[0,-1],[1,0],[0,1])

hole = [
    [],
    [0,1,2,3],
    [0,2],
    [1,3],
    [0,3],
    [2,3],
    [1,2],
    [0,1]
]

if __name__=="__main__":

    T= int(input())

    for tc in range(1,T+1):

        N,M,R,C,L = map(int, input().split())

        board = [list(map(int,input().split())) for _ in range(N)]
        visited = [[0]*M for _ in range(N)]
        # print(*board, sep='\n')

        q= deque([[R,C]])
        visited[R][C]=1
        cnt =1
        
        for _ in range(1,L):
            for _ in range(len(q)):
                pos = q.popleft()
                # print("pos", pos)
                dr = hole[board[pos[0]][pos[1]]]

                for d in dr:
                    nPos = [pos[0]+dirs[d][0], pos[1]+dirs[d][1]]
                    if 0<=nPos[0]<N and 0<=nPos[1]<M and board[nPos[0]][nPos[1]]!=0 and visited[nPos[0]][nPos[1]]!=1:
                        if d ==0:next_dir = 2
                        elif d ==1:next_dir =3
                        elif d==2:next_dir =0
                        elif d==3:next_dir =1
                    
                        if next_dir in hole[board[nPos[0]][nPos[1]]]:
                            q.append([nPos[0], nPos[1]]) #q.append([nPos])
                            cnt+=1
                            visited[nPos[0]][nPos[1]]=1
        print(f'#{tc} {cnt}')


#1 5
#2 15
#3 29
#4 67
#5 71





import sys
from time import time
sys.stdin=open("input.txt","r")
dirs = ([0,-1],[-1,-1],[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1])
sDir = ([-1,0],[0,-1],[1,0],[0,1])
def deepcopy(arr):
    return [[cols[:] for cols in rows] for rows in arr]

def dfs(dep, route,cnt, s, vit):
    global find_route, mCnt
    if dep==3:
        if find_route==[] or cnt>mCnt:
            find_route = route[:]
            mCnt = cnt
        return

    for d in range(4):
        nShark = [s[0]+sDir[d][0], s[1]+sDir[d][1]]
        if 0<=nShark[0]<4 and 0<=nShark[1]<4:
            if vit[nShark[0]][nShark[1]]==1:
                dfs(dep+1, route+[nShark],cnt, nShark,vit)
            else:
                vit[nShark[0]][nShark[1]]=1
                dfs(dep+1, route+[nShark],cnt+len(mBoard[nShark[0]][nShark[1]]), nShark,vit)
                vit[nShark[0]][nShark[1]]=0

if __name__=="__main__":
    start = time()
    M,S = map(int, input().split())
    board = [[[] for _ in range(4)] for _ in range(4)]
    smell = [[0]*4 for _ in range(4)]

    # print(*board, sep='\n')
    for _ in range(M):
        r,c,d = map(int, input().split())
        board[r-1][c-1].append(d-1)
    # print(*board, sep='\n')
    shark = list(map(lambda x : int(x)-1, input().split()))
    # print(shark)

    for _ in range(S):

        cBoard = deepcopy(board)
        mBoard = [[[] for _ in range(4)] for _ in range(4)]

        for i in range(4):
            for j in range(4):
                if board[i][j]:
                    for f in board[i][j]:
                        for t in range(8):
                            next_dir = (f+t*7)%8
                            nPos = [i+dirs[next_dir][0], j+dirs[next_dir][1]]
                            if 0<=nPos[0]<4 and 0<=nPos[1]<4 and smell[nPos[0]][nPos[1]]==0 and nPos!=shark:
                                mBoard[nPos[0]][nPos[1]].append(next_dir)
                                break
                        else:
                            mBoard[i][j].append(f)
        # print()
        # print(*mBoard,sep='\n')

        find_route=[]
        mCnt=0
        visited = [[0]*4 for _ in range(4)]
        dfs(0,[],0, shark, visited)

        # print("shark_route")
        # print(find_route)

        for move in find_route:
            if mBoard[move[0]][move[1]]!=[]:
                smell[move[0]][move[1]]=3
                mBoard[move[0]][move[1]]=[]
        else:
            shark = move

        for i in range(4):
            for j in range(4):
                board[i][j] = mBoard[i][j]+cBoard[i][j]
                if smell[i][j]:
                    smell[i][j]-=1
    
    ans=0
    for i in range(4):
        for j in range(4):
            ans+=len(board[i][j])

    print(ans)
    end=time()
    print(f"time : {end-start}")