You are given a grid with $R$ rows (numbered $1$ through $R$) and $C$ columns (numbered $1$ through $C$). Initially, each cell of this grid is either empty, contains an ant or an anteater. Each ant is moving in a fixed direction: up, down, left or right. The anteaters do not move.
The movement of ants happens in discrete steps. For example, when an ant is in the cell in the $i$-th row and $j$-th column at some point in time (in some step) and it is moving down, then in the next step, it enters the cell in the $(i+1)$-th row and $j$-th column. Two ants meet each other when they enter the same cell at the same point in time (in the same step). When ants meet, they do not interact in any way and keep moving in their fixed directions.
If an ant reaches an anteater, that anteater eats the ant, so the ant completely disappears. If an ant attempts to leave the grid, it also disappears. When two ants enter a cell containing an anteater at the same time, they are eaten before they could meet.
Calculate the total number of pairs of ants that meet each other.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $R$ and $C$.
- Each of the following $R$ lines contains a single string with length $C$. For each valid $i, j$, the $j$-th character in the $i$-th string is:
- '#' if the cell in the $i$-th row and $j$-th column of the grid contains an anteater
- 'U', 'D', 'L' or 'R' if this cell contains an ant moving up, down, left or right respectively
- '-' if this cell is empty

-----Output-----
For each test case, print a single line containing one integer — the number of pairs of ants that meet.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le R, C \le 50$
- each string contains only characters 'U', 'D', 'L', 'R', '#' and '-'

-----Example Input-----
10
3 3
R--
---
--U
1 4
R--R
2 2
--
--
1 4
R--L
1 4
-R-L
1 4
-R#L
3 3
R-D
-#-
R-U
3 3
R-D
---
R#U
3 3
-D-
R-L
-U-
1 7
RLLLLLL

-----Example Output-----
1
0
0
0
1
0
3
2
6
3

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'readFromFile = 0\r\nif readFromFile:\r\n    f = open("inputSmall.txt", "r")\r\n    T = int(f.readline())\r\nelse:\r\n    T = int(input())\r\n\r\ntestCases = range(T)\r\n\r\nfor case in testCases:\r\n    if (readFromFile):\r\n        RC = [int(x) for x in f.readline().split()]\r\n    else:\r\n        RC = [int(x) for x in input().split()]\r\n\r\n    R = RC[0]\r\n    C = RC[1]\r\n\r\n    aByCols = {}\r\n    aByRows = {}\r\n\r\n    uAll = []\r\n    dAll = []\r\n    lAll = []\r\n    rAll = []\r\n    \r\n    for r in range(R):\r\n        if(readFromFile):\r\n            row = f.readline()\r\n        else:\r\n            row = input()\r\n\r\n        for c in range(C):\r\n            if(row[c] == \'#\'):\r\n                if(r not in aByRows):\r\n                    aByRows[r] = []                \r\n                aByRows[r].append(c)\r\n                if(c not in aByCols):\r\n                    aByCols[c] = []\r\n                aByCols[c].append(r)\r\n\r\n            elif(row[c] == \'U\'):\r\n                uAll.append((r,c))\r\n\r\n            elif(row[c] == \'D\'):\r\n                dAll.append((r,c))\r\n\r\n            elif(row[c] == \'L\'):\r\n                lAll.append((r,c))\r\n\r\n            elif(row[c] == \'R\'):\r\n                rAll.append((r,c))\r\n\r\n    # U ant will die if # in same column, smaller row\r\n    for x in range(len(uAll)):\r\n        item = uAll[x]\r\n        r = item[0]\r\n        c = item[1]\r\n        if (c in aByCols):\r\n            eaters = aByCols[c]\r\n        else:\r\n            eaters = []\r\n        age = R\r\n        for y in eaters:\r\n            if (y < r):\r\n                age = min(age, r-y)\r\n        uAll[x] = (item[0], item[1], age)\r\n\r\n    # D ant will die if # in same column, larger row\r\n    for x in range(len(dAll)):\r\n        item = dAll[x]\r\n        r = item[0]\r\n        c = item[1]\r\n        if (c in aByCols):\r\n            eaters = aByCols[c]\r\n        else:\r\n            eaters = []\r\n        age = R\r\n        for y in eaters:\r\n            if (y > r):\r\n                age = min(age, y-r)\r\n        dAll[x] = (item[0], item[1], age)\r\n\r\n    # L ant will die if # in same row, smaller col\r\n    for x in range(len(lAll)):\r\n        item = lAll[x]\r\n        r = item[0]\r\n        c = item[1]\r\n        if (r in aByRows):\r\n            eaters = aByRows[r]\r\n        else:\r\n            eaters = []\r\n        age = C\r\n        for y in eaters:\r\n            if (y < c):\r\n                age = min(age, c-y)\r\n        lAll[x] = (item[0], item[1], age)\r\n\r\n    # R ant will die if # in same row, larger col\r\n    for x in range(len(rAll)):\r\n        item = rAll[x]\r\n        r = item[0]\r\n        c = item[1]\r\n        if (r in aByRows):\r\n            eaters = aByRows[r]\r\n        else:\r\n            eaters = []\r\n        age = C\r\n        for y in eaters:\r\n            if (y > c):\r\n                age = min(age, y-c)\r\n        rAll[x] = (item[0], item[1], age)\r\n\r\n    uBySum = {}\r\n    uByDiff = {}\r\n    uByCol = {}\r\n    \r\n    dBySum = {}\r\n    dByDiff = {}\r\n    dByCol = {}\r\n    \r\n    rBySum = {}\r\n    rByDiff = {}\r\n    rByRow = {}\r\n    \r\n    lBySum = {}\r\n    lByDiff = {}\r\n    lByRow = {}\r\n\r\n    for x in uAll:\r\n        r = x[0]\r\n        c = x[1]\r\n        if (r+c not in uBySum):\r\n            uBySum[r+c] = []\r\n        if (r-c not in uByDiff):\r\n            uByDiff[r-c] = []\r\n        if (c not in uByCol):\r\n            uByCol[c] = []\r\n\r\n        uBySum[r+c].append((r,c,x[2]))\r\n        uByDiff[r-c].append((r,c,x[2]))\r\n        uByCol[c].append((r,c,x[2]))\r\n\r\n    for x in dAll:\r\n        r = x[0]\r\n        c = x[1]\r\n        if (r+c not in dBySum):\r\n            dBySum[r+c] = []\r\n        if (r-c not in dByDiff):\r\n            dByDiff[r-c] = []\r\n        if (c not in dByCol):\r\n            dByCol[c] = []\r\n\r\n        dBySum[r+c].append((r,c,x[2]))\r\n        dByDiff[r-c].append((r,c,x[2]))\r\n        dByCol[c].append((r,c,x[2]))\r\n\r\n    for x in lAll:\r\n        r = x[0]\r\n        c = x[1]\r\n        if (r+c not in lBySum):\r\n            lBySum[r+c] = []\r\n        if (r-c not in lByDiff):\r\n            lByDiff[r-c] = []\r\n        if (r not in lByRow):\r\n            lByRow[r] = []\r\n\r\n        lBySum[r+c].append((r,c,x[2]))\r\n        lByDiff[r-c].append((r,c,x[2]))\r\n        lByRow[r].append((r,c,x[2]))\r\n\r\n    for x in rAll:\r\n        r = x[0]\r\n        c = x[1]\r\n        if (r+c not in rBySum):\r\n            rBySum[r+c] = []\r\n        if (r-c not in rByDiff):\r\n            rByDiff[r-c] = []\r\n        if (r not in rByRow):\r\n            rByRow[r] = []\r\n\r\n        rBySum[r+c].append((r,c,x[2]))\r\n        rByDiff[r-c].append((r,c,x[2]))\r\n        rByRow[r].append((r,c,x[2]))\r\n\r\n    uSums = set(uBySum.keys())\r\n    uDiffs = set(uByDiff.keys())\r\n    uCols = set(uByCol.keys())\r\n    dSums = set(dBySum.keys())\r\n    dDiffs = set(dByDiff.keys())\r\n    dCols = set(dByCol.keys())\r\n    rSums = set(rBySum.keys())\r\n    rDiffs = set(rByDiff.keys())\r\n    rRows = set(rByRow.keys())\r\n    lSums = set(lBySum.keys())\r\n    lDiffs = set(lByDiff.keys())\r\n    lRows = set(lByRow.keys())\r\n\r\n    total = 0\r\n\r\n    ## same sums: possible collision between U and L\r\n    candidates = uSums & lSums\r\n    for cc in candidates:\r\n        r1 = [(x[0], 1, x[2]) for x in uBySum[cc]]\r\n        r2 = [(x[0], 0, x[2]) for x in lBySum[cc]]\r\n        rTot = r1 + r2\r\n        rTot.sort()\r\n\r\n        # Collision only when row of U > row of L\r\n        # both parties survive\r\n        zeros = []\r\n        for i in range(len(rTot)):\r\n            item = rTot[i]\r\n            if (item[1] == 1):\r\n                for j in zeros:\r\n                    if (item[0] - j[0] < j[2]) and (item[0] - j[0] < item[2]):\r\n                        total = total + 1\r\n            elif (item[1] == 0):\r\n                zeros.append(item)\r\n\r\n    ## same sums: possible collision between D and R\r\n    candidates = dSums & rSums\r\n    for cc in candidates:\r\n        r1 = [(x[0], 1, x[2]) for x in rBySum[cc]]\r\n        r2 = [(x[0], 0, x[2]) for x in dBySum[cc]]\r\n        rTot = r1 + r2\r\n        rTot.sort()\r\n\r\n        # Collision only when row of R > row of D\r\n        # both parties survive\r\n        zeros = []\r\n        for i in range(len(rTot)):\r\n            item = rTot[i]\r\n            if (item[1] == 1):\r\n                for j in zeros:\r\n                    if (item[0] - j[0] < j[2]) and (item[0] - j[0] < item[2]):\r\n                        total = total + 1\r\n            elif (item[1] == 0):\r\n                zeros.append(item)\r\n\r\n    ## same diffs: possible collision between U and R\r\n    candidates = uDiffs & rDiffs\r\n    for cc in candidates:\r\n        r1 = [(x[0], 1, x[2]) for x in uByDiff[cc]]\r\n        r2 = [(x[0], 0, x[2]) for x in rByDiff[cc]]\r\n        rTot = r1 + r2\r\n        rTot.sort()\r\n\r\n        # Collision only when row of U > row of R\r\n        # both parties survive\r\n        zeros = []\r\n        for i in range(len(rTot)):\r\n            item = rTot[i]\r\n            if (item[1] == 1):\r\n                for j in zeros:\r\n                    if (item[0] - j[0] < j[2]) and (item[0] - j[0] < item[2]):\r\n                        total = total + 1\r\n            elif (item[1] == 0):\r\n                zeros.append(item)\r\n\r\n    ## same diffs: possible collision between D and L\r\n    candidates = dDiffs & lDiffs\r\n    for cc in candidates:\r\n        r1 = [(x[0], 1, x[2]) for x in lByDiff[cc]]\r\n        r2 = [(x[0], 0, x[2]) for x in dByDiff[cc]]\r\n        rTot = r1 + r2\r\n        rTot.sort()\r\n\r\n        # Collision only when row of L > row of D\r\n        # both parties survive\r\n        zeros = []\r\n        for i in range(len(rTot)):\r\n            item = rTot[i]\r\n            if (item[1] == 1):\r\n                for j in zeros:\r\n                    if (item[0] - j[0] < j[2]) and (item[0] - j[0] < item[2]):\r\n                        total = total + 1\r\n            elif (item[1] == 0):\r\n                zeros.append(item)\r\n\r\n    ## same cols: possible collision between D and U\r\n    candidates = dCols & uCols\r\n    for cc in candidates:\r\n        r1 = [(x[0], 1, x[2]) for x in uByCol[cc]]\r\n        r2 = [(x[0], 0, x[2]) for x in dByCol[cc]]\r\n        rTot = r1 + r2\r\n        rTot.sort()\r\n\r\n        # Collision only when row of U > row of D,\r\n        # distance is even\r\n        # both parties survive\r\n        zeros = []\r\n        for i in range(len(rTot)):\r\n            item = rTot[i]\r\n            if (item[1] == 1):\r\n                for j in zeros:\r\n                    if ((item[0] - j[0]) % 2 == 0) and (item[0] - j[0] < 2*j[2]) and (item[0] - j[0] < 2*item[2]):\r\n                        total = total + 1\r\n            elif (item[1] == 0):\r\n                zeros.append(item)\r\n\r\n    ## same rows: possible collision between L and R\r\n    candidates = lRows & rRows\r\n    for cc in candidates:\r\n        r1 = [(x[1], 1, x[2]) for x in lByRow[cc]]\r\n        r2 = [(x[1], 0, x[2]) for x in rByRow[cc]]\r\n        rTot = r1 + r2\r\n        rTot.sort()\r\n\r\n        # Collision only when col of L > col of R, \r\n        # distance is even\r\n        # both parties survive\r\n        zeros = []\r\n        for i in range(len(rTot)):\r\n            item = rTot[i]\r\n            if (item[1] == 1):\r\n                for j in zeros:\r\n                    if ((item[0] - j[0]) % 2 == 0) and (item[0] - j[0] < 2*j[2]) and (item[0] - j[0] < 2*item[2]):\r\n                        total = total + 1\r\n            elif (item[1] == 0):\r\n                zeros.append(item)\r\n\r\n    print(total)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 30193