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 = 'def check_left_hor(mat, row, col, r,c, z, diff):\n\tif 0<=(z+diff)<c and mat[row][z+diff]=="L":\n\n\t\tfor q in range(z+1, z+diff):\n\t\t\tif mat[row][q] == "#":\n\t\t\t\treturn False\n\n\t\treturn True\n\n\treturn False\n\n\ndef check_left_ver(mat, row, col, r,c, z, diff):\n\tif 0<=(col+diff)<c and mat[z][col+diff]=="L":\n\n\t\tfor q in range(col+1, col+diff):\n\t\t\tif mat[z][q] == "#":\n\t\t\t\treturn False\n\n\t\treturn True\n\n\treturn False\n\n\ndef check_right_hor(mat, row, col, r,c, z, diff):\n\tif 0<=(z-diff)<c and mat[row][z-diff] == "R":\n\n\t\tfor q in range(z-1, z-diff, -1):\n\t\t\tif mat[row][q] == "#":\n\t\t\t\treturn False\n\n\t\treturn True\n\n\treturn False\n\n\ndef check_right_ver(mat, row, col, r,c, z, diff):\n\tif 0<=(col-diff)<c and mat[z][col-diff] == "R":\n\n\t\tfor q in range(col-1, col-diff, -1):\n\t\t\tif mat[z][q] == "#":\n\t\t\t\treturn False\n\n\t\treturn True\n\n\treturn False\n\n\ndef check_down_hor(mat, row, col, r,c, z, diff):\n\tif 0<=(row-diff)<r and mat[row-diff][z] == "D":\n\t\t\n\t\tfor q in range(row-diff, row):\n\t\t\tif mat[q][z] == "#":\n\t\t\t\treturn False\n\n\t\treturn True\n\n\treturn False\n\n\ndef check_down_ver(mat, row, col, r,c, z, diff):\n\tif 0<=(z-diff)<r and mat[z-diff][col] == "D":\n\t\t\n\t\tfor q in range(z-diff, z):\n\t\t\tif mat[q][col] == "#":\n\t\t\t\treturn False\n\n\t\treturn True\n\n\treturn False\n\n\ndef check_up_hor(mat, row, col, r,c, z, diff):\n\t# print(z, row, diff)\n\tif 0<=(row+diff)<r and mat[row+diff][z] == "U":\n\t\tfor q in range(row+1, row+diff):\n\t\t\tif mat[q][z] == "#":\n\t\t\t\treturn False\n\n\t\treturn True\n\n\treturn False\n\ndef check_up_ver(mat, row, col, r,c, z, diff):\n\n\tif 0<=(z+diff)<r and mat[z+diff][col] == "U":\n\t\tfor q in range(z+1, z+diff):\n\t\t\tif mat[q][col] == "#":\n\t\t\t\treturn False\n\n\t\treturn True\n\n\treturn False\n\n\nt = int(input())\n\nfor i in range(t):\n\tr, c = map(int, input().split())\n\n\tmat = []\n\tcount = 0\n\n\tfor j in range(r):\n\t\ttemp = []\n\t\ts = input()\n\n\t\tfor a in range(c):\n\t\t\ttemp.append(s[a])\n\t\t\tif s[a]!="-" and s[a]!="#":\n\t\t\t\t# print(s[a]=="-")\n\t\t\t\tcount+=1\n\n\t\tmat.append(temp)\n\n\t# print(count, mat)\n\tmeets = 0\n\n\tfor row in range(r):\n\n\t\tfor col in range(c):\n\n\t\t\tif mat[row][col]=="-" or mat[row][col]=="#":\n\t\t\t\tcontinue\n\n\t\t\telse:\n\n\t\t\t\tif mat[row][col] == "U":\n\n\t\t\t\t\tfor z in range(row-1, -1, -1):\n\t\t\t\t\t\tif mat[z][col] == "#":\n\t\t\t\t\t\t\tbreak\n\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tdiff = row-z\n\t\t\t\t\t\t\tif check_left_ver(mat, row, col, r, c, z, diff):\n\t\t\t\t\t\t\t\tmeets+=1\n\n\t\t\t\t\t\t\tif check_right_ver(mat, row, col, r, c, z, diff):\n\t\t\t\t\t\t\t\tmeets+=1\n\n\t\t\t\t\t\t\tif check_down_ver(mat, row, col, r, c, z, diff):\n\t\t\t\t\t\t\t\tmeets+=1\n\n\n\t\t\t\tif mat[row][col] == "D":\n\n\t\t\t\t\tfor z in range(row+1, r):\n\t\t\t\t\t\tif mat[z][col] == "#":\n\t\t\t\t\t\t\tbreak\n\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\t# print(col-row+z, col, row, z)\n\t\t\t\t\t\t\tdiff = z-row\n\t\t\t\t\t\t\tif check_left_ver(mat, row, col, r, c, z, diff):\n\t\t\t\t\t\t\t\tmeets+=1\n\n\t\t\t\t\t\t\tif check_right_ver(mat, row, col, r, c, z, diff):\n\t\t\t\t\t\t\t\tmeets+=1\n\n\t\t\t\t\t\t\tif check_up_ver(mat, row, col, r, c, z, diff):\n\t\t\t\t\t\t\t\tmeets+=1\n\n\t\t\t\tif mat[row][col] == "L":\n\n\t\t\t\t\tfor z in range(col-1, -1, -1):\n\t\t\t\t\t\tif mat[row][z] == "#":\n\t\t\t\t\t\t\tbreak\n\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tdiff = col-z\n\t\t\t\t\t\t\t# print(col-row+z, col, row, z)\n\t\t\t\t\t\t\tif check_down_hor(mat, row, col, r, c, z, diff):\n\t\t\t\t\t\t\t\tmeets+=1\n\n\t\t\t\t\t\t\tif check_right_hor(mat, row, col, r, c, z, diff):\n\t\t\t\t\t\t\t\tmeets+=1\n\n\t\t\t\t\t\t\tif check_up_hor(mat, row, col, r, c, z, diff):\n\t\t\t\t\t\t\t\tmeets+=1\n\n\t\t\t\tif mat[row][col] == "R":\n\n\t\t\t\t\tfor z in range(col+1, c):\n\t\t\t\t\t\tif mat[row][z] == "#":\n\t\t\t\t\t\t\tbreak\n\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\t# print(col-row+z, col, row, z)\n\t\t\t\t\t\t\tdiff = z-col\n\t\t\t\t\t\t\tif check_down_hor(mat, row, col, r, c, z, diff):\n\t\t\t\t\t\t\t\tmeets+=1\n\n\t\t\t\t\t\t\tif check_left_hor(mat, row, col, r, c, z, diff):\n\t\t\t\t\t\t\t\tmeets+=1\n\n\n\t\t\t\t\t\t\tif check_up_hor(mat, row, col, r, c, z, diff):\n\t\t\t\t\t\t\t\tmeets+=1\n\n\n\tprint(meets//2)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 15627