There is a rectangular grid of size $n \times m$. Each cell of the grid is colored black ('0') or white ('1'). The color of the cell $(i, j)$ is $c_{i, j}$. You are also given a map of directions: for each cell, there is a direction $s_{i, j}$ which is one of the four characters 'U', 'R', 'D' and 'L'.

  If $s_{i, j}$ is 'U' then there is a transition from the cell $(i, j)$ to the cell $(i - 1, j)$;  if $s_{i, j}$ is 'R' then there is a transition from the cell $(i, j)$ to the cell $(i, j + 1)$;  if $s_{i, j}$ is 'D' then there is a transition from the cell $(i, j)$ to the cell $(i + 1, j)$;  if $s_{i, j}$ is 'L' then there is a transition from the cell $(i, j)$ to the cell $(i, j - 1)$. 

It is guaranteed that the top row doesn't contain characters 'U', the bottom row doesn't contain characters 'D', the leftmost column doesn't contain characters 'L' and the rightmost column doesn't contain characters 'R'.

You want to place some robots in this field (at most one robot in a cell). The following conditions should be satisfied.

  Firstly, each robot should move every time (i.e. it cannot skip the move). During one move each robot goes to the adjacent cell depending on the current direction.  Secondly, you have to place robots in such a way that there is no move before which two different robots occupy the same cell (it also means that you cannot place two robots in the same cell). I.e. if the grid is "RL" (one row, two columns, colors does not matter there) then you can place two robots in cells $(1, 1)$ and $(1, 2)$, but if the grid is "RLL" then you cannot place robots in cells $(1, 1)$ and $(1, 3)$ because during the first second both robots will occupy the cell $(1, 2)$. 

The robots make an infinite number of moves.

Your task is to place the maximum number of robots to satisfy all the conditions described above and among all such ways, you have to choose one where the number of black cells occupied by robots before all movements is the maximum possible. Note that you can place robots only before all movements.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 5 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $m$ ($1 < nm \le 10^6$) — the number of rows and the number of columns correspondingly.

The next $n$ lines contain $m$ characters each, where the $j$-th character of the $i$-th line is $c_{i, j}$ ($c_{i, j}$ is either '0' if the cell $(i, j)$ is black or '1' if the cell $(i, j)$ is white).

The next $n$ lines also contain $m$ characters each, where the $j$-th character of the $i$-th line is $s_{i, j}$ ($s_{i, j}$ is 'U', 'R', 'D' or 'L' and describes the direction of the cell $(i, j)$).

It is guaranteed that the sum of the sizes of fields does not exceed $10^6$ ($\sum nm \le 10^6$).


-----Output-----

For each test case, print two integers — the maximum number of robots you can place to satisfy all the conditions described in the problem statement and the maximum number of black cells occupied by robots before all movements if the number of robots placed is maximized. Note that you can place robots only before all movements.


-----Example-----
Input
3
1 2
01
RL
3 3
001
101
110
RLL
DLD
ULL
3 3
000
000
000
RRD
RLD
ULL

Output
2 1
4 3
2 2

Difficulty: introductory

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def search(i,j):
    L=[]

    c=0

    while CHECK[i][j]==1<<30:
        L.append((i,j))
        
        CHECK[i][j]=c

        if MAP2[i][j]=="U":
            i-=1
        elif MAP2[i][j]=="D":
            i+=1
        elif MAP2[i][j]=="R":
            j+=1
        else:
            j-=1

        c+=1

    if (i,j) in L:
        x=CHECK[i][j]
        y=CHECK[L[-1][0]][L[-1][1]]
        loop=abs(x-y)+1

        for x,y in L:
            CHECK[x][y]%=loop
            LOOP[x][y]=loop

    else:
        loop=LOOP[i][j]
        c=CHECK[i][j]

        for x,y in L[::-1]:
            c=(c-1)%loop
            CHECK[x][y]=c
            LOOP[x][y]=loop

def search2(i,j):
    Q=[(i,j)]
    ANS=[0]*LOOP[i][j]

    while Q:
        x,y=Q.pop()

        if USE[x][y]==1:
            continue
        
        USE[x][y]=1
        if MAP[x][y]=="0":
            ANS[CHECK[x][y]]=1

        if MAP2[x][y]=="U":
            Q.append((x-1,y))
        elif MAP2[x][y]=="D":
            Q.append((x+1,y))
        elif MAP2[x][y]=="R":
            Q.append((x,y+1))
        else:
            Q.append((x,y-1))


        if 0<=x+1<n and 0<=y<m and MAP2[x+1][y]=="U":
            Q.append((x+1,y))
            
        if 0<=x-1<n and 0<=y<m and MAP2[x-1][y]=="D":
            Q.append((x-1,y))
            
        if 0<=x<n and 0<=y+1<m and MAP2[x][y+1]=="L":
            Q.append((x,y+1))
            
        if 0<=x<n and 0<=y-1<m and MAP2[x][y-1]=="R":
            Q.append((x,y-1))

    return LOOP[i][j],sum(ANS)


t=int(input())
for tests in range(t):
    n,m=list(map(int,input().split()))
    MAP=[input().strip() for i in range(n)]
    MAP2=[input().strip() for i in range(n)]

    CHECK=[[1<<30]*m for i in range(n)]
    LOOP=[[1<<30]*m for i in range(n)]

    for i in range(n):
        for j in range(m):
            if CHECK[i][j]==1<<30:
                search(i,j)

                #print(i,j)

    #print(CHECK)
    #print(LOOP)

    USE=[[0]*m for i in range(n)]

    ANSM=0
    ANSC=0

    for i in range(n):
        for j in range(m):
            if USE[i][j]==0:
                x,y=search2(i,j)
                ANSM+=x
                ANSC+=y
    print(ANSM,ANSC)
                
            
    
    


import sys
from collections import deque
input = sys.stdin.readline


t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    s = [input() for i in range(n)]
    grid = [input() for i in range(n)]
    robot_cnt = 0
    black_cnt = 0
    
    graph = [-1] * (n * m)
    rev_graph = [[] for i in range(n * m)]
    for i in range(n):
        for j in range(m):
            if grid[i][j] == "U":
                graph[i * m + j] = (i - 1) * m + j
                rev_graph[(i - 1) * m + j].append(i * m + j)
            elif grid[i][j] == "R":
                graph[i * m + j] = i * m + (j + 1)
                rev_graph[i * m + (j + 1)].append(i * m + j)
            elif grid[i][j] == "D":
                graph[i * m + j] = (i + 1) * m + j
                rev_graph[(i + 1) * m + j].append(i * m + j)
            elif grid[i][j] == "L":
                graph[i * m + j] = i * m + (j - 1)
                rev_graph[i * m + (j - 1)].append(i * m + j)

    is_start = [True] * (n * m)
    for i in graph:
        is_start[i] = False

    is_cycle = [False] * (n * m)
    period = [0] * (n * m)
    for i in range(n * m):
        if not is_start[i]:
            continue
        st = i
        period[i] = 1
        while True:
            nxt_i = graph[i]
            if period[nxt_i] < 0:
                tmp = period[nxt_i]
                break
            if period[nxt_i] > 0:
                tmp = -(period[i] - period[nxt_i] + 1)
                is_cycle[nxt_i] = True
                break
            period[graph[i]] = period[i] + 1
            i = graph[i]
        i = st
        period[i] = tmp
        while True:
            nxt_i = graph[i]
            if period[nxt_i] < 0:
                break
            period[graph[i]] = tmp
            i = graph[i]

    # cycle without side road
    for i in range(n * m):
        if period[i] == 0:
            robot_cnt += 1
            if s[i // m][i % m] == "0":
                black_cnt += 1
                
    # cycle with road
    for i in range(n * m):
        if not is_cycle[i]:
            continue
        MOD = - period[i]
        period[i] = 0
        is_black = [False] * MOD
        if s[i // m][i % m] == "0":
            is_black[0] = True
        q = deque([i])
        while q:
            v = q.pop()
            for nxt_v in rev_graph[v]:
                if period[nxt_v] >= 0:
                    continue
                period[nxt_v] = (period[v] + 1) % MOD
                if s[nxt_v // m][nxt_v % m] == "0":
                    is_black[period[nxt_v]] = True
                q.append(nxt_v)  
        robot_cnt += MOD
        black_cnt += sum(is_black)

    print(robot_cnt, black_cnt)

import sys

_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__



def go():
    # n = int(input())
    n,m = list(map(int, input().split()))
    c=''.join(input() for _ in range(n))
    s=''.join(input() for _ in range(n))

    nm = n * m
    done = [False] * nm
    groups = [None] * nm
    phase = [-1]*nm

    def step(pos,direct=None):
        if direct is None:
            direct=s[pos]
        if direct=='U':
            return pos-m
        if direct=='D':
            return pos+m
        if direct=='L':
            return pos-1
        if direct=='R':
            return pos+1

    cyc_len={}

    for i in range(nm):
        if not done[i]:
            same = {}
            pos=0
            cur=i
            group=-1
            pcur=None
            while cur not in same:
                if groups[cur] is not None:
                    group=groups[cur]
                    pcur=pos+phase[cur]
                    break
                same[cur]=pos
                done[cur]=True
                cur=step(cur)
                pos+=1
            else:
                group=cur
                cyc_len[group]=len(same)-same[cur]
                pcur=pos

            for ss,pos in list(same.items()):
                groups[ss]=group
                phase[ss]=(pcur-pos)%cyc_len[group]

    blacks =  len(set((pp,gg)for cc,pp,gg in zip(c,phase,groups) if cc=='0'))
    # print('ppp',phase)
    # print(groups)
    # print('--',cyc_len)

    return f'{sum(cyc_len.values())} {blacks}'

# x,s = map(int,input().split())
t = int(input())
# t = 1
ans = []
for _ in range(t):
    # print(go())
    ans.append(str(go()))
#
print('\n'.join(ans))


import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    for _ in range(II()):
        h,w=MI()
        cc=[list(map(int,list(SI()))) for _ in range(h)]
        ss=[SI() for _ in range(h)]
        aa=[[0]*w for _ in range(h)]
        mm=[[0]*w for _ in range(h)]
        cyc=[0]
        ci=1
        dir="UDLR"
        dij=[(-1,0),(1,0),(0,-1),(0,1)]
        for si in range(h):
            for sj in range(w):
                if aa[si][sj]!=0:continue
                i,j=si,sj
                d=-1
                stack=[]
                while aa[i][j]==0:
                    aa[i][j]=d
                    stack.append((i,j))
                    d-=1
                    di,dj=dij[dir.index(ss[i][j])]
                    i,j=i+di,j+dj
                if aa[i][j]>0:
                    a=aa[i][j]
                    dist=cyc[a]
                    m=(mm[i][j]+1)%dist
                    for i,j in stack[::-1]:
                        aa[i][j]=a
                        mm[i][j]=m
                        m=(m+1)%dist
                else:
                    dist=aa[i][j]-d
                    cyc.append(dist)
                    m=0
                    for i, j in stack[::-1]:
                        aa[i][j] = ci
                        mm[i][j]=m
                        m=(m+1)%dist
                    ci+=1
        #print(cyc)
        #p2D(aa)
        one=[set() for _ in range(ci)]
        for i in range(h):
            for j in range(w):
                if cc[i][j]==0:
                    one[aa[i][j]].add(mm[i][j])
        #print(one)
        ans1=sum(cyc)
        ans2=sum(min(ck,len(ok)) for ck,ok in zip(cyc,one))
        print(ans1,ans2)

main()

import sys

_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__



def go():
    # n = int(input())
    n,m = map(int, input().split())
    c=''.join(input() for _ in range(n))
    s=''.join(input() for _ in range(n))

    nm = n * m
    done = [False] * nm
    groups = [None] * nm
    phase = [-1]*nm

    def step(pos,direct=None):
        if direct is None:
            direct=s[pos]
        if direct=='U':
            return pos-m
        if direct=='D':
            return pos+m
        if direct=='L':
            return pos-1
        if direct=='R':
            return pos+1

    cyc_len={}

    for i in range(nm):
        if not done[i]:
            same = {}
            pos=0
            cur=i
            group=-1
            pcur=None
            while cur not in same:
                if groups[cur] is not None:
                    group=groups[cur]
                    pcur=pos+phase[cur]
                    break
                same[cur]=pos
                done[cur]=True
                cur=step(cur)
                pos+=1
            else:
                group=cur
                cyc_len[group]=len(same)-same[cur]
                pcur=pos

            for ss,pos in same.items():
                groups[ss]=group
                phase[ss]=(pcur-pos)%cyc_len[group]

    blacks =  len(set((pp,gg)for cc,pp,gg in zip(c,phase,groups) if cc=='0'))
    # print('ppp',phase)
    # print(groups)
    # print('--',cyc_len)

    return f'{sum(cyc_len.values())} {blacks}'

# x,s = map(int,input().split())
t = int(input())
# t = 1
ans = []
for _ in range(t):
    # print(go())
    ans.append(str(go()))
#
print('\n'.join(ans))

import sys
from collections import deque
import gc


def findCycle(source, getNbr):
    q = deque([source])
    parent = {source: None}
    while q:
        node = q.popleft()
        for nbr in getNbr(node):
            if nbr not in parent:
                q.append(nbr)
                parent[nbr] = node
            else:
                cycle = [node]
                while parent[node] != nbr:
                    node = parent[node]
                    cycle.append(node)
                cycle.append(nbr)
                return cycle[::-1]


def markTime(cycle, getNbr):
    cycleLen = len(cycle)
    q = deque(cycle)
    dist = {x: cycleLen - 1 - i for i, x in enumerate(cycle)} # distance to reach cycle[-1]
    while q:
        node = q.popleft()
        d = dist[node]
        for nbr in getNbr(node):
            if nbr not in dist:
                q.append(nbr)
                dist[nbr] = (d + 1) % cycleLen
    return dist


def solve(R, C, grid, directions):
    BLACK = 0
    drdc = {
        "U": [-1, 0],
        "R": [0, 1],
        "D": [1, 0],
        "L": [0, -1],
    }

    def getNbr(i):
        r, c = divmod(i, C)
        dr, dc = drdc[directions[r][c]]
        return [(r + dr) * C + (c + dc)]

    def getNbrT(i):
        r, c = divmod(i, C)
        ret = []
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr = r + dr
            nc = c + dc
            if 0 <= nr < R and 0 <= nc < C:
                if [-dr, -dc] == drdc[directions[nr][nc]]:
                    ret.append(nr * C + nc)
        return ret

    ans1 = 0
    ans2 = 0
    seen = set()
    for i in range(R * C):
        if i not in seen:
            # BFS until found cycle
            cycle = findCycle(i, getNbr)
            uniqueTimes = len(cycle)
            # Find all nodes going to cycle
            # Each starting node going into cycle will have a collision timestamp mod cycle len
            dist = markTime(cycle, getNbrT)
            uniqueBlackTimes = set()
            for j, t in list(dist.items()):
                r, c = divmod(j, C)
                if grid[r][c] == BLACK:
                    uniqueBlackTimes.add(t)
                seen.add(j)
            ans1 += uniqueTimes
            ans2 += len(uniqueBlackTimes)
            del cycle
            del dist
            del uniqueBlackTimes

    return str(ans1) + " " + str(ans2)


def __starting_point():
    input = sys.stdin.readline

    T = int(input())
    for t in range(T):
        R, C = [int(x) for x in input().split()]
        grid = [list(map(int, input().rstrip())) for r in range(R)]
        directions = [list(input().rstrip()) for r in range(R)]

        ans = solve(R, C, grid, directions)
        print(ans)

__starting_point()