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 = '# Contest Code: PRACTICE      Problem Code: ANTEATER\n#\n# Author: Keyur Shroff\n# Date: 24 June 2019\n\nimport math\nfrom collections import defaultdict\n\n# --- Function to calculate nCr\ndef nCr(n,r):\n    f = math.factorial\n    return (f(n) // f(r)) // f(n-r)\n\n# --- Main Program ---\ndef main() :\n    t = int(input())\n    for _ in range(t) :\n        r, c = map(int, input().split())\n        matrix = []\n        for i in range(r) :\n            data = list(input())\n            matrix.append(data)\n        \n        timeHorizon = defaultdict(int)\n        for i in range(r) :\n            for j in range(c) :\n                if (matrix[i][j] == "U") :\n                    step = 1\n                    for k in range(i-1, -1, -1) :\n                        if (matrix[k][j] == "#") :\n                            break\n                        timeHorizon[(step,k,j)] += 1\n                        step += 1\n                elif (matrix[i][j] == "D") :\n                    step = 1\n                    for k in range(i+1, r, 1) :\n                        if (matrix[k][j] == "#") :\n                            break\n                        timeHorizon[(step,k,j)] += 1\n                        step += 1\n                elif (matrix[i][j] == "L") :\n                    step = 1\n                    for k in range(j-1, -1, -1) :\n                        if (matrix[i][k] == "#") :\n                            break\n                        timeHorizon[(step,i,k)] += 1\n                        step += 1\n                elif (matrix[i][j] == "R") :\n                    step = 1\n                    for k in range(j+1, c, 1) :\n                        if (matrix[i][k] == "#") :\n                            break\n                        timeHorizon[(step,i,k)] += 1\n                        step += 1\n        \n        # Count total number of pairs of ants that meet each other\n        count = 0\n        for key in timeHorizon :\n            if (timeHorizon[key] > 1) :\n                ants = timeHorizon[key]\n                count += nCr(ants, 2)\n        \n        print(count)\n\n\ndef __starting_point():\n    #import profile\n    #profile.run(\'main()\')\n    main()\n    \n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 15527