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

Difficulty: HARD
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(r, c) = map(int, input().split())
	a = [input() for _ in range(r)]
	ans = 0
	for (i, row) in enumerate(a):
		for (j, x) in enumerate(row):
			if x == 'R':
				for (k, y) in enumerate(row[j + 1:]):
					if y == '#':
						break
					if k % 2 and y == 'L':
						ans += 1
			elif x in 'UD':
				b = a[i + 1:] if x == 'D' else a[:i][::-1]
				for (k, row1) in enumerate(b, 1):
					if row1[j] == '#':
						break
					if k % 2 == 0 and x + row1[j] == 'UD':
						ans += 1
					m = j - k
					if m >= 0 and row1[m] == 'R' and ('#' not in row1[m + 1:j]):
						ans += 1
					m = j + k
					if m < c and row1[m] == 'L' and ('#' not in row1[j + 1:m]):
						ans += 1
	print(ans)


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	d = []
	s = 0
	for _ in range(r):
		a = input()
		a = [i for i in a]
		d.append(a)
	for i in range(r):
		for j in range(c):
			if d[i][j] == 'R':
				for k in range(j, c):
					if d[i][k] == '#':
						break
					elif d[i][k] == 'L' and (not k - j & 1):
						s += 1
				l = i + 1
				k = j + 1
				while k < c and l < r:
					f = 0
					if d[l][k] == 'U':
						for m in range(j, k + 1):
							if d[i][m] == '#':
								f = 1
								break
						if f == 0:
							for m in range(i, l + 1):
								if d[m][k] == '#':
									f = 1
									break
						if f == 0:
							s += 1
					k += 1
					l += 1
			elif d[i][j] == 'L':
				l = i + 1
				k = j - 1
				while l < r and k > -1:
					if d[l][k] == 'U':
						f = 0
						for m in range(j, k - 1, -1):
							if d[i][m] == '#':
								f = 1
								break
						if f == 0:
							for m in range(i, l + 1):
								if d[m][k] == '#':
									f = 1
									break
						if f == 0:
							s += 1
					l += 1
					k -= 1
			elif d[i][j] == 'D':
				for m in range(i, r):
					if d[m][j] == '#':
						break
					elif d[m][j] == 'U' and (not m - i & 1):
						s += 1
				l = i + 1
				k = j + 1
				while l < r and k < c:
					f = 0
					if d[l][k] == 'L':
						for m in range(i, l + 1):
							if d[m][j] == '#':
								f = 1
								break
						if f == 0:
							for m in range(j, k + 1):
								if d[l][m] == '#':
									f = 1
									break
						if f == 0:
							s += 1
					l += 1
					k += 1
				l = i + 1
				k = j - 1
				while l < r and k > -1:
					f = 0
					if d[l][k] == 'R':
						for m in range(i, l + 1):
							if d[m][j] == '#':
								f = 1
								break
						if f == 0:
							for m in range(k, j + 1):
								if d[l][m] == '#':
									f = 1
									break
						if f == 0:
							s += 1
					l += 1
					k -= 1
	print(s)


from collections import Counter
t = int(input())
for _ in range(t):
	(r, c) = map(int, input().split())
	d = dict()
	for i in range(r):
		for j in range(c):
			d[i, j] = []
	grid = []
	for i in range(r):
		x = input()
		x = [j for j in x]
		grid += [x]
	for i in range(r):
		for j in range(c):
			if grid[i][j] == 'U':
				k = i
				time = 0
				while k >= 0:
					if grid[k][j] == '#':
						break
					else:
						d[k, j] += [time]
					k -= 1
					time += 1
			elif grid[i][j] == 'D':
				k = i
				time = 0
				while k < r:
					if grid[k][j] == '#':
						break
					else:
						d[k, j] += [time]
					k += 1
					time += 1
			elif grid[i][j] == 'R':
				k = j
				time = 0
				while k < c:
					if grid[i][k] == '#':
						break
					else:
						d[i, k] += [time]
					k += 1
					time += 1
			elif grid[i][j] == 'L':
				k = j
				time = 0
				while k >= 0:
					if grid[i][k] == '#':
						break
					else:
						d[i, k] += [time]
					k -= 1
					time += 1
	ans = 0
	for i in d:
		freq = dict(Counter(d[i]))
		for j in freq:
			if freq[j] > 1:
				ans += freq[j] * (freq[j] - 1) // 2
	print(ans)


from collections import defaultdict
from math import factorial
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	hash = defaultdict(int)
	for i in range(n):
		k = list(input())
		l.append(k)
	ans = 0
	for i in range(n):
		for j in range(m):
			count = 0
			if l[i][j] == 'R':
				x = i
				y = j
				while y < m:
					if l[x][y] != '#':
						hash[count, x, y] += 1
					else:
						break
					count += 1
					y += 1
			elif l[i][j] == 'L':
				x = i
				y = j
				count = 0
				while y >= 0:
					if l[x][y] != '#':
						hash[count, x, y] += 1
					else:
						break
					count += 1
					y -= 1
			elif l[i][j] == 'U':
				x = i
				y = j
				count = 0
				while x >= 0:
					if l[x][y] != '#':
						hash[count, x, y] += 1
					else:
						break
					count += 1
					x -= 1
			elif l[i][j] == 'D':
				x = i
				y = j
				count = 0
				while x < n:
					if l[x][y] != '#':
						hash[count, x, y] += 1
					else:
						break
					count += 1
					x += 1
	for i in hash.keys():
		z = hash[i]
		if z > 1:
			ans += factorial(z) // (factorial(z - 2) * factorial(2))
	print(ans)


def check_left_hor(mat, row, col, r, c, z, diff):
	if 0 <= z + diff < c and mat[row][z + diff] == 'L':
		for q in range(z + 1, z + diff):
			if mat[row][q] == '#':
				return False
		return True
	return False

def check_left_ver(mat, row, col, r, c, z, diff):
	if 0 <= col + diff < c and mat[z][col + diff] == 'L':
		for q in range(col + 1, col + diff):
			if mat[z][q] == '#':
				return False
		return True
	return False

def check_right_hor(mat, row, col, r, c, z, diff):
	if 0 <= z - diff < c and mat[row][z - diff] == 'R':
		for q in range(z - 1, z - diff, -1):
			if mat[row][q] == '#':
				return False
		return True
	return False

def check_right_ver(mat, row, col, r, c, z, diff):
	if 0 <= col - diff < c and mat[z][col - diff] == 'R':
		for q in range(col - 1, col - diff, -1):
			if mat[z][q] == '#':
				return False
		return True
	return False

def check_down_hor(mat, row, col, r, c, z, diff):
	if 0 <= row - diff < r and mat[row - diff][z] == 'D':
		for q in range(row - diff, row):
			if mat[q][z] == '#':
				return False
		return True
	return False

def check_down_ver(mat, row, col, r, c, z, diff):
	if 0 <= z - diff < r and mat[z - diff][col] == 'D':
		for q in range(z - diff, z):
			if mat[q][col] == '#':
				return False
		return True
	return False

def check_up_hor(mat, row, col, r, c, z, diff):
	if 0 <= row + diff < r and mat[row + diff][z] == 'U':
		for q in range(row + 1, row + diff):
			if mat[q][z] == '#':
				return False
		return True
	return False

def check_up_ver(mat, row, col, r, c, z, diff):
	if 0 <= z + diff < r and mat[z + diff][col] == 'U':
		for q in range(z + 1, z + diff):
			if mat[q][col] == '#':
				return False
		return True
	return False
t = int(input())
for i in range(t):
	(r, c) = map(int, input().split())
	mat = []
	count = 0
	for j in range(r):
		temp = []
		s = input()
		for a in range(c):
			temp.append(s[a])
			if s[a] != '-' and s[a] != '#':
				count += 1
		mat.append(temp)
	meets = 0
	for row in range(r):
		for col in range(c):
			if mat[row][col] == '-' or mat[row][col] == '#':
				continue
			else:
				if mat[row][col] == 'U':
					for z in range(row - 1, -1, -1):
						if mat[z][col] == '#':
							break
						else:
							diff = row - z
							if check_left_ver(mat, row, col, r, c, z, diff):
								meets += 1
							if check_right_ver(mat, row, col, r, c, z, diff):
								meets += 1
							if check_down_ver(mat, row, col, r, c, z, diff):
								meets += 1
				if mat[row][col] == 'D':
					for z in range(row + 1, r):
						if mat[z][col] == '#':
							break
						else:
							diff = z - row
							if check_left_ver(mat, row, col, r, c, z, diff):
								meets += 1
							if check_right_ver(mat, row, col, r, c, z, diff):
								meets += 1
							if check_up_ver(mat, row, col, r, c, z, diff):
								meets += 1
				if mat[row][col] == 'L':
					for z in range(col - 1, -1, -1):
						if mat[row][z] == '#':
							break
						else:
							diff = col - z
							if check_down_hor(mat, row, col, r, c, z, diff):
								meets += 1
							if check_right_hor(mat, row, col, r, c, z, diff):
								meets += 1
							if check_up_hor(mat, row, col, r, c, z, diff):
								meets += 1
				if mat[row][col] == 'R':
					for z in range(col + 1, c):
						if mat[row][z] == '#':
							break
						else:
							diff = z - col
							if check_down_hor(mat, row, col, r, c, z, diff):
								meets += 1
							if check_left_hor(mat, row, col, r, c, z, diff):
								meets += 1
							if check_up_hor(mat, row, col, r, c, z, diff):
								meets += 1
	print(meets // 2)


import math as mt

def countPairs(arr, n):
	mp = dict()
	for i in range(n):
		if arr[i] in mp.keys():
			mp[arr[i]] += 1
		else:
			mp[arr[i]] = 1
	ans = 0
	for it in mp:
		count = mp[it]
		ans += count * (count - 1) // 2
	return ans
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	has = []
	simple = []
	for i in range(r):
		lis = input()
		lis = list(lis)
		for j in range(c):
			if lis[j] == '#':
				has.append([i, j])
			elif lis[j] != '-':
				simple.append([lis[j], [i, j]])
	sum1 = 0
	for j in range(max(r, c)):
		(he, del1) = ([], [])
		flag = 0
		for i in simple:
			if i[0] == 'R' and i[1][1] + j + 1 <= c:
				if has.count([i[1][0], i[1][1] + j + 1]) == 0:
					he.append((i[1][0], i[1][1] + j + 1))
				else:
					del1.append(i)
			elif i[0] == 'D' and i[1][0] + j + 1 <= r:
				if has.count([i[1][0] + j + 1, i[1][1]]) == 0:
					he.append((i[1][0] + j + 1, i[1][1]))
				else:
					del1.append(i)
			elif i[0] == 'L' and i[1][1] - j - 1 >= 0:
				if has.count([i[1][0], i[1][1] - j - 1]) == 0:
					he.append((i[1][0], i[1][1] - j - 1))
				else:
					del1.append(i)
			elif i[0] == 'U' and i[1][0] - j - 1 >= 0:
				if has.count([i[1][0] - j - 1, i[1][1]]) == 0:
					he.append((i[1][0] - j - 1, i[1][1]))
				else:
					del1.append(i)
		sum1 += countPairs(he, len(he))
		for p in del1:
			simple.remove(p)
	print(sum1)


def kk(L):
	c = 1
	ans = 0
	dp = []
	for i in range(1, len(L)):
		if L[i] != L[i - 1]:
			dp.append(c)
			c = 1
		else:
			c += 1
	dp.append(c)
	for i in range(0, len(dp)):
		ans += dp[i] * (dp[i] - 1) // 2
	return ans
T = int(input())
for i in range(0, T):
	(R, C) = map(int, input().split())
	arr = []
	for j in range(R):
		s = input()
		arr.append(s)
	ans = []
	for j in range(R):
		h = []
		for k in range(C):
			g = []
			h.append(g)
		ans.append(h)
	c = 0
	for j in range(R):
		for k in range(C):
			if arr[j][k] != '#' and arr[j][k] != '-':
				c += 1
				d = arr[j][k]
				if d == 'R':
					ptr1 = j
					ptr2 = k
					cnt = 0
					while ptr1 >= 0 and ptr1 < R and (ptr2 >= 0) and (ptr2 < C):
						if ptr1 >= 0 and ptr1 < R and (ptr2 >= 0) and (ptr2 < C) and (arr[ptr1][ptr2] != '#'):
							ans[ptr1][ptr2].append(cnt)
						else:
							break
						cnt += 1
						ptr2 += 1
				elif d == 'L':
					ptr1 = j
					ptr2 = k
					cnt = 0
					while ptr1 >= 0 and ptr1 < R and (ptr2 >= 0) and (ptr2 < C):
						if ptr1 >= 0 and ptr1 < R and (ptr2 >= 0) and (ptr2 < C) and (arr[ptr1][ptr2] != '#'):
							ans[ptr1][ptr2].append(cnt)
						else:
							break
						cnt += 1
						ptr2 -= 1
				elif d == 'D':
					ptr1 = j
					ptr2 = k
					cnt = 0
					while ptr1 >= 0 and ptr1 < R and (ptr2 >= 0) and (ptr2 < C):
						if ptr1 >= 0 and ptr1 < R and (ptr2 >= 0) and (ptr2 < C) and (arr[ptr1][ptr2] != '#'):
							ans[ptr1][ptr2].append(cnt)
						else:
							break
						cnt += 1
						ptr1 += 1
				elif d == 'U':
					ptr1 = j
					ptr2 = k
					cnt = 0
					while ptr1 >= 0 and ptr1 < R and (ptr2 >= 0) and (ptr2 < C):
						if ptr1 >= 0 and ptr1 < R and (ptr2 >= 0) and (ptr2 < C) and (arr[ptr1][ptr2] != '#'):
							ans[ptr1][ptr2].append(cnt)
						else:
							break
						cnt += 1
						ptr1 -= 1
	fnl = 0
	for j in range(R):
		for k in range(C):
			p = ans[j][k]
			ans[j][k] = sorted(ans[j][k])
	for j in range(R):
		for k in range(C):
			p = ans[j][k]
			fnl += kk(p)
	print(fnl)


T = int(input())
while T > 0:
	(R, C) = input().split()
	R = int(R)
	C = int(C)
	output = [[0] * C for i in range(R)]
	for i in range(R):
		for j in range(C):
			output[i][j] = dict()
	matrix = [0] * R
	for i in range(R):
		matrix[i] = input()
	for i in range(R):
		for j in range(C):
			if matrix[i][j] == 'R':
				column = j + 1
				while column < C and matrix[i][column] != '#':
					output[i][column][column - j] = output[i][column].get(column - j, 0) + 1
					column = column + 1
			elif matrix[i][j] == 'L':
				column = j - 1
				while column >= 0 and matrix[i][column] != '#':
					output[i][column][j - column] = output[i][column].get(j - column, 0) + 1
					column = column - 1
			elif matrix[i][j] == 'U':
				row = i - 1
				while row >= 0 and matrix[row][j] != '#':
					output[row][j][i - row] = output[row][j].get(i - row, 0) + 1
					row = row - 1
			elif matrix[i][j] == 'D':
				row = i + 1
				while row < R and matrix[row][j] != '#':
					output[row][j][row - i] = output[row][j].get(row - i, 0) + 1
					row = row + 1
	no_of_pairs = 0
	for i in range(R):
		for j in range(C):
			for (no_of_steps, count) in output[i][j].items():
				if count > 1:
					no_of_pairs = no_of_pairs + count * (count - 1) // 2
	print(no_of_pairs)
	T = T - 1


import copy

def AllDead(arr):
	var = 1
	for x in arr:
		for y in x:
			if 'U' in y or 'D' in y or 'L' in y or ('R' in y):
				var = 0
	return var

def checkMeet(arr):
	ans = 0
	for x in arr:
		for y in x:
			if len(y) >= 2 and '-' not in y:
				ans += len(y) * (len(y) - 1) // 2
	return ans
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	lol = [['#']] * (m + 2)
	arr = [lol]
	for j in range(n):
		mo = [[x] for x in input()]
		arr += [[['#']] + mo + [['#']]]
	arr += [lol]
	meet = 0
	while AllDead(arr) == 0:
		temp = copy.deepcopy(arr)
		for x in range(1, n + 1):
			for y in range(1, m + 1):
				for z in arr[x][y]:
					if z == 'U':
						if arr[x - 1][y] == ['#']:
							do_nothing = 1
						elif temp[x - 1][y] == ['-']:
							temp[x - 1][y].remove('-')
							temp[x - 1][y] += ['U']
						else:
							temp[x - 1][y] += ['U']
						temp[x][y].remove(z)
						if len(temp[x][y]) == 0:
							temp[x][y] = ['-']
					if z == 'D':
						if arr[x + 1][y] == ['#']:
							do_nothing = 1
						elif temp[x + 1][y] == ['-']:
							temp[x + 1][y].remove('-')
							temp[x + 1][y] += ['D']
						else:
							temp[x + 1][y] += ['D']
						temp[x][y].remove(z)
						if len(temp[x][y]) == 0:
							temp[x][y] = ['-']
					if z == 'L':
						if arr[x][y - 1] == ['#']:
							do_nothing = 1
						elif temp[x][y - 1] == ['-']:
							temp[x][y - 1].remove('-')
							temp[x][y - 1] += ['L']
						else:
							temp[x][y - 1] += ['L']
						temp[x][y].remove(z)
						if len(temp[x][y]) == 0:
							temp[x][y] = ['-']
					if z == 'R':
						if arr[x][y + 1] == ['#']:
							do_nothing = 1
						elif temp[x][y + 1] == ['-']:
							temp[x][y + 1].remove('-')
							temp[x][y + 1] += ['R']
						else:
							temp[x][y + 1] += ['R']
						temp[x][y].remove(z)
						if len(temp[x][y]) == 0:
							temp[x][y] = ['-']
		arr = copy.deepcopy(temp)
		meet += checkMeet(arr)
	print(meet)


T = int(input())
for t in range(T):
	(R, C) = [int(i) for i in input().split()]
	right = []
	left = []
	up = []
	down = []
	ant = []
	sm = 0
	for r in range(R):
		s = input()
		c = 0
		for i in s:
			if i == 'R':
				right.append([r, c])
			elif i == 'L':
				left.append([r, c])
			elif i == 'U':
				up.append([r, c])
			elif i == 'D':
				down.append([r, c])
			elif i == '#':
				ant.append([r, c])
			else:
				pass
			c += 1
	a = len(right)
	b = len(left)
	c = len(up)
	d = len(down)
	while True:
		if a + b + c + d == 0:
			break
		for i in range(a):
			x = right[i]
			y = x[1]
			y += 1
			if y == C:
				right[i] = [-1, -1]
			else:
				z = x[0]
				right[i] = [z, y]
				if right[i] in ant:
					right[i] = [-1, -1]
		for i in range(b):
			x = left[i]
			y = x[1]
			y -= 1
			if y == -1:
				left[i] = [-1, -1]
			else:
				z = x[0]
				left[i] = [z, y]
				if left[i] in ant:
					left[i] = [-1, -1]
		for i in range(c):
			x = up[i]
			y = x[0]
			y -= 1
			if y == -1:
				up[i] = [-1, -1]
			else:
				z = x[1]
				up[i] = [y, z]
				if up[i] in ant:
					up[i] = [-1, -1]
		for i in range(d):
			if down[i] != [-1, -1]:
				x = down[i]
				y = x[0]
				y += 1
				if y == R:
					down[i] = [-1, -1]
				else:
					z = x[1]
					down[i] = [y, z]
					if down[i] in ant:
						down[i] = [-1, -1]
		q = 0
		while True:
			if q >= a:
				break
			if right[q] == [-1, -1]:
				del right[q]
				a -= 1
			else:
				q += 1
		w = 0
		while True:
			if w >= b:
				break
			if left[w] == [-1, -1]:
				del left[w]
				b -= 1
			else:
				w += 1
		e = 0
		while True:
			if e >= c:
				break
			if up[e] == [-1, -1]:
				del up[e]
				c -= 1
			else:
				e += 1
		p = 0
		while True:
			if p >= d:
				break
			if down[p] == [-1, -1]:
				del down[p]
				d -= 1
			else:
				p += 1
		for i in right:
			if i in left:
				sm += 1
			if i in up:
				sm += 1
			if i in down:
				sm += 1
		for i in left:
			if i in up:
				sm += 1
			if i in down:
				sm += 1
		for i in up:
			if i in down:
				sm += 1
	print(sm)


t = int(input())
for x in range(t):
	(r, c) = map(int, input().split())
	antU = []
	antD = []
	antR = []
	antL = []
	anteater = []
	j = 0
	for y in range(r):
		s = input()
		i = 0
		for z in s:
			if z == 'U':
				antU.append([j, i, 0, i])
			elif z == 'D':
				antD.append([j, i, r - 1, i])
			elif z == 'R':
				antR.append([j, i, j, c - 1])
			elif z == 'L':
				antL.append([j, i, j, 0])
			elif z == '#':
				anteater.append([j, i])
			i = i + 1
		j = j + 1
	for y in anteater:
		for z in antU:
			if y[1] == z[1] and z[0] > y[0] and (z[2] <= y[0]):
				z[2] = y[0] + 1
		for z in antD:
			if y[1] == z[1] and z[0] < y[0] and (z[2] >= y[0]):
				z[2] = y[0] - 1
		for z in antR:
			if y[0] == z[0] and z[1] < y[1] and (z[3] >= y[1]):
				z[3] = y[1] - 1
		for z in antL:
			if y[0] == z[0] and z[1] > y[1] and (z[3] <= y[1]):
				z[3] = y[1] + 1
	total = 0
	for y in antU:
		for z in antD:
			if y[1] == z[1] and y[2] <= z[2] and (y[0] > z[0]):
				if (y[0] - z[0]) % 2 == 0:
					total = total + 1
		for z in antR:
			if y[1] - z[1] == y[0] - z[0]:
				if y[2] <= z[0] and z[3] >= y[1]:
					if y[0] > z[0] and y[1] > z[1]:
						total = total + 1
		for z in antL:
			if y[1] - z[1] == z[0] - y[0]:
				if z[3] <= y[1] and y[2] <= z[0]:
					if y[0] > z[0] and y[1] < z[1]:
						total = total + 1
	for y in antL:
		for z in antR:
			if (y[1] - z[1]) % 2 == 0:
				if y[0] == z[0] and y[3] <= z[3] and (y[1] > z[1]):
					total = total + 1
		for z in antD:
			if y[0] - z[0] == y[1] - z[1]:
				if y[3] <= z[1] and z[2] >= y[0]:
					if y[0] > z[0] and y[1] > z[1]:
						total = total + 1
	for y in antD:
		for z in antR:
			if y[0] - z[0] == z[1] - y[1]:
				if z[3] >= y[1] and y[2] >= z[0]:
					if y[0] < z[0] and y[1] > z[1]:
						total = total + 1
	print(total)


def main():
	for _ in range(int(input())):
		(r, c) = map(int, input().split())
		g = list()
		ants = list()
		eaters = set()
		dd = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
		for i in range(r):
			g.append(list(input().strip()))
			for j in range(c):
				if g[i][j] in 'UDLR':
					ants.append((i, j, dd[g[i][j]]))
				elif g[i][j] == '#':
					eaters.add((i, j))
		count = 0
		while len(ants) != 0:
			nants = list()
			nc = dict()
			for k in ants:
				nk = (k[0] + k[2][0], k[1] + k[2][1])
				if nk not in eaters and min(nk) >= 0 and (nk[0] < r) and (nk[1] < c):
					nants.append((nk[0], nk[1], k[2]))
					if nk not in nc:
						nc[nk] = 1
					else:
						nc[nk] += 1
			ants = nants
			for (i, k) in nc.items():
				count += k * (k - 1) // 2
		print(count)
main()


def nCr(n, r):
	return fact(n) / (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	board = []
	for i in range(r):
		x = input()
		board.append(x)
	coll = []
	for i in range(r):
		coll.append([])
		for j in range(c):
			coll[i].append([])
	for i in range(r):
		for j in range(c):
			if board[i][j] == '-' or board[i][j] == '#':
				pass
			else:
				cnt = 1
				if board[i][j] == 'D':
					for k in range(i + 1, r):
						if board[k][j] == '#':
							break
						coll[k][j].append(cnt)
						cnt += 1
				if board[i][j] == 'U':
					for k in range(i - 1, -1, -1):
						if board[k][j] == '#':
							break
						coll[k][j].append(cnt)
						cnt += 1
				if board[i][j] == 'R':
					for k in range(j + 1, c):
						if board[i][k] == '#':
							break
						coll[i][k].append(cnt)
						cnt += 1
				if board[i][j] == 'L':
					for k in range(j - 1, -1, -1):
						if board[i][k] == '#':
							break
						coll[i][k].append(cnt)
						cnt += 1
	coll_cnt = 0
	for i in range(r):
		for j in range(c):
			if len(coll[i][j]) > 1:
				set_coll_i_j = set(coll[i][j])
				cnt_dict = {}
				for k in set_coll_i_j:
					cnt_dict[k] = 0
				for k in coll[i][j]:
					cnt_dict[k] += 1
				for k in cnt_dict.values():
					if k > 1:
						coll_cnt += int(nCr(k, 2))
	print(coll_cnt)


from collections import Counter
t = int(input())
for _ in range(t):
	(r, c) = map(int, input().split())
	grid = {(i, j): [] for i in range(r) for j in range(c)}
	cmd = []
	for i in range(r):
		for j in range(c):
			grid[i, j] = []
	for i in range(r):
		move = input()
		cmd.append([i for i in move])
	for i in range(r):
		for j in range(c):
			if cmd[i][j] == 'R':
				k = j
				time = 0
				while k < c:
					if cmd[i][k] == '#':
						break
					else:
						grid[i, k] += [time]
					time += 1
					k += 1
			if cmd[i][j] == 'L':
				k = j
				time = 0
				while k >= 0:
					if cmd[i][k] == '#':
						break
					else:
						grid[i, k] += [time]
					time += 1
					k -= 1
			if cmd[i][j] == 'U':
				k = i
				time = 0
				while k >= 0:
					if cmd[k][j] == '#':
						break
					else:
						grid[k, j] += [time]
					time += 1
					k -= 1
			if cmd[i][j] == 'D':
				k = i
				time = 0
				while k < r:
					if cmd[k][j] == '#':
						break
					else:
						grid[k, j] += [time]
					time += 1
					k += 1
	meet = 0
	for i in grid:
		f = dict(Counter(grid[i]))
		for j in f:
			if f[j] > 1:
				meet += (f[j] * f[j] - f[j]) // 2
	print(meet)


from collections import defaultdict as df
t = int(input())
for x in range(t):
	(r, c) = list(map(int, input().split()))
	p = df(list)
	a = [[0] * c for i in range(r)]
	for i in range(r):
		s = input().rstrip()
		for j in range(c):
			a[i][j] = s[j]
	for i in range(r):
		for j in range(c):
			timer = 0
			if a[i][j] == 'U':
				for k in range(i - 1, -1, -1):
					if a[k][j] != '#':
						timer += 1
						p[str(k) + ' ' + str(j)].append(timer)
					else:
						break
			if a[i][j] == 'R':
				for k in range(j + 1, c):
					if a[i][k] != '#':
						timer += 1
						p[str(i) + ' ' + str(k)].append(timer)
					else:
						break
			if a[i][j] == 'D':
				for k in range(i + 1, r):
					if a[k][j] != '#':
						timer += 1
						p[str(k) + ' ' + str(j)].append(timer)
					else:
						break
			if a[i][j] == 'L':
				for k in range(j - 1, -1, -1):
					if a[i][k] != '#':
						timer += 1
						p[str(i) + ' ' + str(k)].append(timer)
					else:
						break
	total = 0
	for i in p:
		y = set(p[i])
		for j in y:
			if p[i].count(j) > 1:
				n1 = p[i].count(j)
				total += n1 * (n1 - 1) // 2
	print(total)


def find_next(arr):
	ans = [[set() for i in range(len(arr[0]))] for j in range(len(arr))]
	for i in range(len(arr)):
		for j in range(len(arr[0])):
			if j > 0:
				if 'R' in arr[i][j - 1] and '#' not in arr[i][j]:
					ans[i][j].add('R')
			if j < len(arr[0]) - 1:
				if 'L' in arr[i][j + 1] and '#' not in arr[i][j]:
					ans[i][j].add('L')
			if i > 0:
				if 'D' in arr[i - 1][j] and '#' not in arr[i][j]:
					ans[i][j].add('D')
			if i < len(arr) - 1:
				if 'U' in arr[i + 1][j] and '#' not in arr[i][j]:
					ans[i][j].add('U')
			if '#' in arr[i][j]:
				ans[i][j].add('#')
	return ans

def cal(arr):
	ans = 0
	for i in range(len(arr)):
		for j in range(len(arr[0])):
			n = len(arr[i][j])
			ans += n * (n - 1) // 2
	return ans
t = int(input())
for _ in range(t):
	(r, c) = list(map(int, input().split()))
	arr = []
	for i in range(r):
		toadd = list(map(set, list(input())))
		arr += [toadd]
	ans = 0
	for i in range(max(r, c)):
		arr = find_next(arr)
		ans += cal(arr)
	print(ans)


t = int(input())
for _ in range(t):
	(r, c) = map(int, input().split())
	a = [input() for _ in range(r)]
	ans = 0
	for i in range(r):
		for j in range(c):
			if a[i][j] == 'L':
				for k in range(j - 1, -1, -1):
					if a[i][k] == '#':
						break
					if k % 2 == j % 2 and a[i][k] == 'R':
						ans += 1
					m = i - j + k
					if m >= 0 and a[m][k] == 'D' and all((a[ii][k] != '#' for ii in range(m + 1, i))):
						ans += 1
					m = i + j - k
					if m < r and a[m][k] == 'U' and all((a[ii][k] != '#' for ii in range(i + 1, m))):
						ans += 1
			elif a[i][j] == 'R':
				for k in range(j + 1, c):
					if a[i][k] == '#':
						break
					m = i - k + j
					if m >= 0 and a[m][k] == 'D' and all((a[ii][k] != '#' for ii in range(m + 1, i))):
						ans += 1
					m = i + k - j
					if m < r and a[m][k] == 'U' and all((a[ii][k] != '#' for ii in range(i + 1, m))):
						ans += 1
			elif a[i][j] == 'D':
				for k in range(i + 1, r):
					if a[k][j] == '#':
						break
					if k % 2 == i % 2 and a[k][j] == 'U':
						ans += 1
	print(ans)


from bisect import *
from collections import *
from itertools import *
import functools
import sys
from math import *
from decimal import *
from copy import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 10 ** 5 + 10
MOD = 10 ** 9 + 7

def isprime(n):
	n = abs(int(n))
	if n < 2:
		return False
	if n == 2:
		return True
	if not n & 1:
		return False
	for x in range(3, int(n ** 0.5) + 1, 2):
		if n % x == 0:
			return False
	return True

def mhd(a, b):
	return abs(a[0] - b[0]) + abs(b[1] - a[1])

def charIN(x=' '):
	return sys.stdin.readline().strip().split(x)

def arrIN(x=' '):
	return list(map(int, sys.stdin.readline().strip().split(x)))

def eld(x, y):
	a = y[0] - x[0]
	b = x[1] - y[1]
	return (a * a + b * b) ** 0.5

def lgcd(a):
	g = a[0]
	for i in range(1, len(a)):
		g = math.gcd(g, a[i])
	return g

def ms(a):
	msf = -MAX
	meh = 0
	st = en = be = 0
	for i in range(len(a)):
		meh += a[i]
		if msf < meh:
			msf = meh
			st = be
			en = i
		if meh < 0:
			meh = 0
			be = i + 1
	return (msf, st, en)

def flush():
	return sys.stdout.flush()

def nc2(n):
	return n * (n - 1) // 2
for _ in range(int(input())):
	(r, c) = arrIN()
	a = [[i for i in input().strip()] for _ in range(r)]
	x = [[[0 for k in range(100)] for i in range(c)] for j in range(r)]
	for i in range(r):
		for j in range(c):
			if a[i][j] == 'U':
				q = 1
				for k in range(i - 1, -1, -1):
					if a[k][j] == '#':
						break
					x[k][j][q] += 1
					q += 1
			elif a[i][j] == 'D':
				q = 1
				for k in range(i + 1, r):
					if a[k][j] == '#':
						break
					x[k][j][q] += 1
					q += 1
			elif a[i][j] == 'R':
				q = 1
				for k in range(j + 1, c):
					if a[i][k] == '#':
						break
					x[i][k][q] += 1
					q += 1
			elif a[i][j] == 'L':
				q = 1
				for k in range(j - 1, -1, -1):
					if a[i][k] == '#':
						break
					x[i][k][q] += 1
					q += 1
	ans = 0
	for i in range(r):
		for j in range(c):
			for k in range(100):
				ans += nc2(x[i][j][k])
	print(ans)


def get_matrix(r, c):
	matrix = []
	for i in range(r):
		oneline = list(input())
		matrix.append(oneline)
	return matrix

def get_empty_matrix(r, c):
	new_matrix = []
	for i in range(r):
		oneline = ['' for k in range(c)]
		new_matrix.append(oneline)
	return new_matrix

def rectify_newmat(new_matrix, r, c):
	for i in range(r):
		for j in range(c):
			if len(new_matrix[i][j]) == 0:
				new_matrix[i][j] = '-'
	return new_matrix

def handle_one():
	(r, c) = map(int, input().split())
	matrix = get_matrix(r, c)
	meetups = 0
	max_movements = max(r, c)
	for lol in range(max_movements):
		new_matrix = get_empty_matrix(r, c)
		for i in range(r):
			for j in range(c):
				for p in range(len(matrix[i][j])):
					if matrix[i][j][p] == '-':
						pass
					elif matrix[i][j][p] == 'U':
						if i != 0:
							new_matrix[i - 1][j] += 'U'
					elif matrix[i][j][p] == 'D':
						if i != r - 1:
							new_matrix[i + 1][j] += 'D'
					elif matrix[i][j][p] == 'R':
						if j != c - 1:
							new_matrix[i][j + 1] += 'R'
					elif matrix[i][j][p] == 'L':
						if j != 0:
							new_matrix[i][j - 1] += 'L'
					elif matrix[i][j][p] == '#':
						new_matrix[i][j] = '#'
		new_matrix = rectify_newmat(new_matrix, r, c)
		for i in range(r):
			for j in range(c):
				if '#' in new_matrix[i][j]:
					new_matrix[i][j] = '#'
				elif len(new_matrix[i][j]) >= 2:
					n = len(new_matrix[i][j])
					added_meetups = n * (n - 1) // 2
					meetups += added_meetups
		matrix = list(new_matrix)
	print(meetups)
T = int(input())
for ds in range(T):
	handle_one()


import sys
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for _ in range(n):
		a.append(list(input()))
	b = [[[0] * 50 for i in range(m)] for i in range(n)]
	for i in range(n):
		for j in range(m):
			t = 0
			if a[i][j] == 'U':
				for k in range(i, -1, -1):
					if a[k][j] == '#':
						break
					b[k][j][t] += 1
					t += 1
			elif a[i][j] == 'D':
				for k in range(i, n):
					if a[k][j] == '#':
						break
					b[k][j][t] += 1
					t += 1
			elif a[i][j] == 'R':
				for k in range(j, m):
					if a[i][k] == '#':
						break
					b[i][k][t] += 1
					t += 1
			elif a[i][j] == 'L':
				for k in range(j, -1, -1):
					if a[i][k] == '#':
						break
					b[i][k][t] += 1
					t += 1
	ans = 0
	for i in range(n):
		for j in range(m):
			if a[i][j] != '#':
				for k in range(50):
					ans += b[i][j][k] * (b[i][j][k] - 1) // 2
	print(ans)


t = int(input())
for numtest in range(1, t + 1):
	(n, m) = [int(k) for k in input().strip().split(' ')]
	g = []
	ants = []
	dd = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
	anteaters = set()
	for i in range(n):
		g += [input().strip()]
		for j in range(m):
			if g[i][j] in 'UDLR':
				ants += [(i, j, dd[g[i][j]])]
			if g[i][j] == '#':
				anteaters.add((i, j))
	nbm = 0
	while len(ants):
		nants = []
		nc = {}
		for k in ants:
			nk = (k[0] + k[2][0], k[1] + k[2][1])
			if nk not in anteaters and min(nk[0], nk[1]) >= 0 and (nk[0] < n) and (nk[1] < m):
				nants += [(nk[0], nk[1], k[2])]
				if nk not in nc:
					nc[nk] = 1
				else:
					nc[nk] += 1
		ants = nants
		for (i, k) in nc.items():
			nbm += k * (k - 1) // 2
	print(nbm)


import copy
for t in range(int(input())):
	(r, c) = list(map(int, input().split()))
	grid = []
	cpy = []
	for i in range(r):
		grid.append(list(input()))
	change = True
	ans = 0
	while change:
		cpy = [['' for i in range(c)] for j in range(r)]
		change = False
		for i in range(r):
			for j in range(c):
				for ele in grid[i][j]:
					if ele == 'D' and i < r - 1:
						change = True
						if grid[i + 1][j] != '#':
							cpy[i + 1][j] += 'D'
					elif ele == 'U' and i > 0:
						change = True
						if grid[i - 1][j] != '#':
							cpy[i - 1][j] += 'U'
					elif ele == 'R' and j < c - 1:
						change = True
						if grid[i][j + 1] != '#':
							cpy[i][j + 1] += 'R'
					elif ele == 'L' and j > 0:
						change = True
						if grid[i][j - 1] != '#':
							cpy[i][j - 1] += 'L'
					elif ele == '#':
						cpy[i][j] = '#'
		for i in range(r):
			for j in range(c):
				s = cpy[i][j]
				ans += len(s) * (len(s) - 1) / 2
				grid[i][j] = s
	print(int(ans))


import math
from collections import defaultdict

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)

def main():
	t = int(input())
	for _ in range(t):
		(r, c) = map(int, input().split())
		matrix = []
		for i in range(r):
			data = list(input())
			matrix.append(data)
		timeHorizon = defaultdict(int)
		for i in range(r):
			for j in range(c):
				if matrix[i][j] == 'U':
					step = 1
					for k in range(i - 1, -1, -1):
						if matrix[k][j] == '#':
							break
						timeHorizon[step, k, j] += 1
						step += 1
				elif matrix[i][j] == 'D':
					step = 1
					for k in range(i + 1, r, 1):
						if matrix[k][j] == '#':
							break
						timeHorizon[step, k, j] += 1
						step += 1
				elif matrix[i][j] == 'L':
					step = 1
					for k in range(j - 1, -1, -1):
						if matrix[i][k] == '#':
							break
						timeHorizon[step, i, k] += 1
						step += 1
				elif matrix[i][j] == 'R':
					step = 1
					for k in range(j + 1, c, 1):
						if matrix[i][k] == '#':
							break
						timeHorizon[step, i, k] += 1
						step += 1
		count = 0
		for key in timeHorizon:
			if timeHorizon[key] > 1:
				ants = timeHorizon[key]
				count += nCr(ants, 2)
		print(count)
main()


t = int(input())
for i in range(t):
	(r, c) = map(int, input().split())
	arr = [['' for x in range(c)] for y in range(r)]
	for j in range(r):
		arr[j] = list(str(input()))
	anr = ['U', 'D', 'L', 'R']
	meet = 0
	pos = [[[0 for z in range(c)] for y in range(r)] for x in range(max(r, c))]
	j = 0
	k = 0
	while j < r:
		j_init = j
		k = 0
		while k < c:
			k_init = k
			if arr[j][k] in anr:
				for z in range(max(r, c)):
					if j == r or k == c or arr[j][k] == '#' or (k == -1) or (j == -1):
						break
					if pos[z][j][k] > 0:
						meet += pos[z][j][k]
					pos[z][j][k] += 1
					if arr[j_init][k_init] == 'D':
						j += 1
					elif arr[j_init][k_init] == 'U':
						j -= 1
					elif arr[j_init][k_init] == 'L':
						k -= 1
					elif arr[j_init][k_init] == 'R':
						k += 1
			k = k_init + 1
			j = j_init
		j = j_init + 1
	print(meet)


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	board = []
	for i in range(r):
		x = input()
		board.append(x)
	coll = []
	for i in range(r):
		coll.append([])
		for j in range(c):
			coll[i].append([])
	for i in range(r):
		for j in range(c):
			if board[i][j] == '-' or board[i][j] == '#':
				pass
			else:
				cnt = 1
				if board[i][j] == 'D':
					for k in range(i + 1, r):
						if board[k][j] == '#':
							break
						coll[k][j].append(cnt)
						cnt += 1
				if board[i][j] == 'U':
					for k in range(i - 1, -1, -1):
						if board[k][j] == '#':
							break
						coll[k][j].append(cnt)
						cnt += 1
				if board[i][j] == 'R':
					for k in range(j + 1, c):
						if board[i][k] == '#':
							break
						coll[i][k].append(cnt)
						cnt += 1
				if board[i][j] == 'L':
					for k in range(j - 1, -1, -1):
						if board[i][k] == '#':
							break
						coll[i][k].append(cnt)
						cnt += 1
	cnts = 0
	for i in range(r):
		for j in range(c):
			if len(coll[i][j]) > 1:
				sets = set(coll[i][j])
				counts = {}
				for k in sets:
					counts[k] = 0
				for k in coll[i][j]:
					counts[k] += 1
				for k in counts.values():
					if k > 1:
						cnts += int(k * (k - 1) // 2)
	print(cnts)


for i in range(int(input())):
	(r, c) = [int(a) for a in input().split()]
	a = []
	for i in range(r):
		a.append(input())
	n = max(r, c)
	lst = [0 for i in range(n)]
	complete_list = []
	for i in range(r):
		z = []
		for j in range(c):
			z.append(lst.copy())
		complete_list.append(z)
	for i in range(r):
		for j in range(c):
			if a[i][j] == 'R':
				l = 1
				for p in range(j + 1, c):
					if a[i][p] == '#':
						break
					complete_list[i][p][l] += 1
					l += 1
			elif a[i][j] == 'L':
				l = 1
				for p in range(j - 1, -1, -1):
					if a[i][p] == '#':
						break
					complete_list[i][p][l] += 1
					l += 1
			elif a[i][j] == 'D':
				l = 1
				for p in range(i + 1, r):
					if a[p][j] == '#':
						break
					complete_list[p][j][l] += 1
					l += 1
			elif a[i][j] == 'U':
				l = 1
				for p in range(i - 1, -1, -1):
					if a[p][j] == '#':
						break
					complete_list[p][j][l] += 1
					l += 1
	ans = 0
	for i in range(r):
		for j in range(c):
			for p in range(n):
				if complete_list[i][j][p] == 2:
					ans += 1
				elif complete_list[i][j][p] == 3:
					ans += 3
				elif complete_list[i][j][p] == 4:
					ans += 6
	print(ans)


import copy
T = int(input())
while T:
	(R, C) = map(int, input().split())
	A = []
	for i in range(R):
		B = input()
		A.append(B)
	ans = 0
	for x in range(R):
		for y in range(C):
			if A[x][y] != '#':
				dist = []
				a = copy.deepcopy(x)
				b = copy.deepcopy(y)
				while a >= 0:
					if A[a][b] == 'D':
						dist.append(x - a)
					if A[a][b] == '#':
						break
					a -= 1
				a = copy.deepcopy(x)
				b = copy.deepcopy(y)
				while a < R:
					if A[a][b] == 'U':
						dist.append(a - x)
					if A[a][b] == '#':
						break
					a += 1
				a = copy.deepcopy(x)
				b = copy.deepcopy(y)
				while b >= 0:
					if A[a][b] == 'R':
						dist.append(y - b)
					if A[a][b] == '#':
						break
					b -= 1
				a = copy.deepcopy(x)
				b = copy.deepcopy(y)
				while b < C:
					if A[a][b] == 'L':
						dist.append(b - y)
					if A[a][b] == '#':
						break
					b += 1
				dist.sort()
				j = 0
				count = 0
				while j < len(dist) - 1:
					if dist[j] != dist[j + 1]:
						ans += count * (count + 1) // 2
						count = 0
					if dist[j] == dist[j + 1]:
						count += 1
					j += 1
				ans += count * (count + 1) // 2
	print(ans)
	T -= 1


t = int(input())
while t:
	t -= 1
	(r, c) = map(int, input().split())
	arr = []
	for i in range(r):
		s = list(input())
		arr.append(s)
	ans = 0
	for i in range(r):
		for j in range(c):
			if arr[i][j] == 'R':
				row = i
				column = j
				u = 0
				if column < c - 1:
					flag2 = False
					for k in range(column + 1, c):
						u += 1
						if flag2 == False:
							if row - u >= 0:
								flag = False
								for g in range(row - 1, row - u, -1):
									if arr[g][k] == '#':
										flag = True
										break
								if flag == False:
									if arr[row - u][k] == 'D':
										ans += 1
							if row + u < r:
								flag1 = False
								for g in range(row + 1, row + u):
									if arr[g][k] == '#':
										flag1 = True
										break
								if flag1 == False:
									if arr[row + u][k] == 'U':
										ans += 1
						if arr[row][k] == '#':
							flag2 = True
							if row - u >= 0:
								if arr[row - u][k] == 'D' and flag == False:
									ans -= 1
							if row + u < r:
								if arr[row + u][k] == 'U' and flag1 == False:
									ans -= 1
							break
						elif flag2 == False:
							if (k - column) % 2 == 0 and arr[row][k] == 'L':
								ans += 1
				arr[i][j] = '0'
			elif arr[i][j] == 'L':
				row = i
				column = j
				u = 0
				if column > 0:
					flag2 = False
					for k in range(column - 1, -1, -1):
						u += 1
						if flag2 == False:
							if row - u >= 0:
								flag = False
								for g in range(row - 1, row - u, -1):
									if arr[g][k] == '#':
										flag = True
										break
								if flag == False:
									if arr[row - u][k] == 'D':
										ans += 1
							if row + u < r:
								flag1 = False
								for g in range(row + 1, row + u):
									if arr[g][k] == '#':
										flag1 = True
										break
								if flag1 == False:
									if arr[row + u][k] == 'U':
										ans += 1
						if arr[row][k] == '#':
							flag2 = True
							if row - u >= 0:
								if arr[row - u][k] == 'D' and flag == False:
									ans -= 1
							if row + u < r:
								if arr[row + u][k] == 'U' and flag1 == False:
									ans -= 1
							break
						elif flag2 == False:
							if (column - k) % 2 == 0 and arr[row][k] == 'R':
								ans += 1
				arr[i][j] = '0'
			elif arr[i][j] == 'U':
				row = i
				column = j
				u = 0
				if row > 0:
					flag2 = False
					for k in range(row - 1, -1, -1):
						u += 1
						if flag2 == False:
							if column - u >= 0:
								flag = False
								for g in range(column - 1, column - u, -1):
									if arr[k][g] == '#':
										flag = True
										break
								if flag == False:
									if arr[k][column - u] == 'R':
										ans += 1
							if column + u < c:
								flag1 = False
								for g in range(column + 1, column + u):
									if arr[k][g] == '#':
										flag1 = True
										break
								if flag1 == False:
									if arr[k][column + u] == 'L':
										ans += 1
						if arr[k][column] == '#':
							flag2 = True
							if column - u >= 0:
								if arr[k][column - u] == 'R' and flag == False:
									ans -= 1
							if column + u < c:
								if arr[k][column + u] == 'L' and flag1 == False:
									ans -= 1
							break
						elif flag2 == False:
							if (row - k) % 2 == 0 and arr[k][column] == 'D':
								ans += 1
				arr[i][j] = '0'
			elif arr[i][j] == 'D':
				row = i
				column = j
				u = 0
				if row < r - 1:
					flag2 = False
					for k in range(row + 1, r):
						u += 1
						if flag2 == False:
							if column - u >= 0:
								flag = False
								for g in range(column - 1, column - u, -1):
									if arr[k][g] == '#':
										flag = True
										break
								if flag == False:
									if arr[k][column - u] == 'R':
										ans += 1
							if column + u < c:
								flag1 = False
								for g in range(column + 1, column + u):
									if arr[k][g] == '#':
										flag1 = True
										break
								if flag1 == False:
									if arr[k][column + u] == 'L':
										ans += 1
						if arr[k][column] == '#':
							flag2 = True
							if column - u >= 0:
								if arr[k][column - u] == 'R' and flag == False:
									ans -= 1
							if column + u < c:
								if arr[k][column + u] == 'L' and flag1 == False:
									ans -= 1
							break
						elif flag2 == False:
							if (k - row) % 2 == 0 and arr[k][column] == 'U':
								ans += 1
				arr[i][j] = '0'
	print(ans)


readFromFile = 0
if readFromFile:
	f = open('inputSmall.txt', 'r')
	T = int(f.readline())
else:
	T = int(input())
testCases = range(T)
for case in testCases:
	if readFromFile:
		RC = [int(x) for x in f.readline().split()]
	else:
		RC = [int(x) for x in input().split()]
	R = RC[0]
	C = RC[1]
	aByCols = {}
	aByRows = {}
	uAll = []
	dAll = []
	lAll = []
	rAll = []
	for r in range(R):
		if readFromFile:
			row = f.readline()
		else:
			row = input()
		for c in range(C):
			if row[c] == '#':
				if r not in aByRows:
					aByRows[r] = []
				aByRows[r].append(c)
				if c not in aByCols:
					aByCols[c] = []
				aByCols[c].append(r)
			elif row[c] == 'U':
				uAll.append((r, c))
			elif row[c] == 'D':
				dAll.append((r, c))
			elif row[c] == 'L':
				lAll.append((r, c))
			elif row[c] == 'R':
				rAll.append((r, c))
	for x in range(len(uAll)):
		item = uAll[x]
		r = item[0]
		c = item[1]
		if c in aByCols:
			eaters = aByCols[c]
		else:
			eaters = []
		age = R
		for y in eaters:
			if y < r:
				age = min(age, r - y)
		uAll[x] = (item[0], item[1], age)
	for x in range(len(dAll)):
		item = dAll[x]
		r = item[0]
		c = item[1]
		if c in aByCols:
			eaters = aByCols[c]
		else:
			eaters = []
		age = R
		for y in eaters:
			if y > r:
				age = min(age, y - r)
		dAll[x] = (item[0], item[1], age)
	for x in range(len(lAll)):
		item = lAll[x]
		r = item[0]
		c = item[1]
		if r in aByRows:
			eaters = aByRows[r]
		else:
			eaters = []
		age = C
		for y in eaters:
			if y < c:
				age = min(age, c - y)
		lAll[x] = (item[0], item[1], age)
	for x in range(len(rAll)):
		item = rAll[x]
		r = item[0]
		c = item[1]
		if r in aByRows:
			eaters = aByRows[r]
		else:
			eaters = []
		age = C
		for y in eaters:
			if y > c:
				age = min(age, y - c)
		rAll[x] = (item[0], item[1], age)
	uBySum = {}
	uByDiff = {}
	uByCol = {}
	dBySum = {}
	dByDiff = {}
	dByCol = {}
	rBySum = {}
	rByDiff = {}
	rByRow = {}
	lBySum = {}
	lByDiff = {}
	lByRow = {}
	for x in uAll:
		r = x[0]
		c = x[1]
		if r + c not in uBySum:
			uBySum[r + c] = []
		if r - c not in uByDiff:
			uByDiff[r - c] = []
		if c not in uByCol:
			uByCol[c] = []
		uBySum[r + c].append((r, c, x[2]))
		uByDiff[r - c].append((r, c, x[2]))
		uByCol[c].append((r, c, x[2]))
	for x in dAll:
		r = x[0]
		c = x[1]
		if r + c not in dBySum:
			dBySum[r + c] = []
		if r - c not in dByDiff:
			dByDiff[r - c] = []
		if c not in dByCol:
			dByCol[c] = []
		dBySum[r + c].append((r, c, x[2]))
		dByDiff[r - c].append((r, c, x[2]))
		dByCol[c].append((r, c, x[2]))
	for x in lAll:
		r = x[0]
		c = x[1]
		if r + c not in lBySum:
			lBySum[r + c] = []
		if r - c not in lByDiff:
			lByDiff[r - c] = []
		if r not in lByRow:
			lByRow[r] = []
		lBySum[r + c].append((r, c, x[2]))
		lByDiff[r - c].append((r, c, x[2]))
		lByRow[r].append((r, c, x[2]))
	for x in rAll:
		r = x[0]
		c = x[1]
		if r + c not in rBySum:
			rBySum[r + c] = []
		if r - c not in rByDiff:
			rByDiff[r - c] = []
		if r not in rByRow:
			rByRow[r] = []
		rBySum[r + c].append((r, c, x[2]))
		rByDiff[r - c].append((r, c, x[2]))
		rByRow[r].append((r, c, x[2]))
	uSums = set(uBySum.keys())
	uDiffs = set(uByDiff.keys())
	uCols = set(uByCol.keys())
	dSums = set(dBySum.keys())
	dDiffs = set(dByDiff.keys())
	dCols = set(dByCol.keys())
	rSums = set(rBySum.keys())
	rDiffs = set(rByDiff.keys())
	rRows = set(rByRow.keys())
	lSums = set(lBySum.keys())
	lDiffs = set(lByDiff.keys())
	lRows = set(lByRow.keys())
	total = 0
	candidates = uSums & lSums
	for cc in candidates:
		r1 = [(x[0], 1, x[2]) for x in uBySum[cc]]
		r2 = [(x[0], 0, x[2]) for x in lBySum[cc]]
		rTot = r1 + r2
		rTot.sort()
		zeros = []
		for i in range(len(rTot)):
			item = rTot[i]
			if item[1] == 1:
				for j in zeros:
					if item[0] - j[0] < j[2] and item[0] - j[0] < item[2]:
						total = total + 1
			elif item[1] == 0:
				zeros.append(item)
	candidates = dSums & rSums
	for cc in candidates:
		r1 = [(x[0], 1, x[2]) for x in rBySum[cc]]
		r2 = [(x[0], 0, x[2]) for x in dBySum[cc]]
		rTot = r1 + r2
		rTot.sort()
		zeros = []
		for i in range(len(rTot)):
			item = rTot[i]
			if item[1] == 1:
				for j in zeros:
					if item[0] - j[0] < j[2] and item[0] - j[0] < item[2]:
						total = total + 1
			elif item[1] == 0:
				zeros.append(item)
	candidates = uDiffs & rDiffs
	for cc in candidates:
		r1 = [(x[0], 1, x[2]) for x in uByDiff[cc]]
		r2 = [(x[0], 0, x[2]) for x in rByDiff[cc]]
		rTot = r1 + r2
		rTot.sort()
		zeros = []
		for i in range(len(rTot)):
			item = rTot[i]
			if item[1] == 1:
				for j in zeros:
					if item[0] - j[0] < j[2] and item[0] - j[0] < item[2]:
						total = total + 1
			elif item[1] == 0:
				zeros.append(item)
	candidates = dDiffs & lDiffs
	for cc in candidates:
		r1 = [(x[0], 1, x[2]) for x in lByDiff[cc]]
		r2 = [(x[0], 0, x[2]) for x in dByDiff[cc]]
		rTot = r1 + r2
		rTot.sort()
		zeros = []
		for i in range(len(rTot)):
			item = rTot[i]
			if item[1] == 1:
				for j in zeros:
					if item[0] - j[0] < j[2] and item[0] - j[0] < item[2]:
						total = total + 1
			elif item[1] == 0:
				zeros.append(item)
	candidates = dCols & uCols
	for cc in candidates:
		r1 = [(x[0], 1, x[2]) for x in uByCol[cc]]
		r2 = [(x[0], 0, x[2]) for x in dByCol[cc]]
		rTot = r1 + r2
		rTot.sort()
		zeros = []
		for i in range(len(rTot)):
			item = rTot[i]
			if item[1] == 1:
				for j in zeros:
					if (item[0] - j[0]) % 2 == 0 and item[0] - j[0] < 2 * j[2] and (item[0] - j[0] < 2 * item[2]):
						total = total + 1
			elif item[1] == 0:
				zeros.append(item)
	candidates = lRows & rRows
	for cc in candidates:
		r1 = [(x[1], 1, x[2]) for x in lByRow[cc]]
		r2 = [(x[1], 0, x[2]) for x in rByRow[cc]]
		rTot = r1 + r2
		rTot.sort()
		zeros = []
		for i in range(len(rTot)):
			item = rTot[i]
			if item[1] == 1:
				for j in zeros:
					if (item[0] - j[0]) % 2 == 0 and item[0] - j[0] < 2 * j[2] and (item[0] - j[0] < 2 * item[2]):
						total = total + 1
			elif item[1] == 0:
				zeros.append(item)
	print(total)


tt = int(input())
for ii in range(tt):
	(r, c) = map(int, input().split())
	arr = []
	for jj in range(r):
		temp = input()
		temp = list(temp)
		t1 = []
		for kk in temp:
			t1.append([kk])
		arr.append(t1)
	t = 0
	cnt = 0
	while t <= max(r, c) + 1:
		temp = [[['-'] for i in range(c)] for j in range(r)]
		for jj in range(r):
			for kk in range(c):
				if arr[jj][kk][0] == '#':
					temp[jj][kk] = arr[jj][kk]
				elif arr[jj][kk][0] == '-':
					pass
				else:
					li = arr[jj][kk]
					le = len(li)
					for pp in range(le):
						if li[pp] == 'U' and jj == 0:
							pass
						elif li[pp] == 'U':
							if arr[jj - 1][kk][0] == '#':
								pass
							elif temp[jj - 1][kk][0] == '-':
								temp[jj - 1][kk][0] = 'U'
							else:
								temp[jj - 1][kk].append('U')
						if li[pp] == 'D' and jj == r - 1:
							pass
						elif li[pp] == 'D':
							if arr[jj + 1][kk][0] == '#':
								pass
							elif temp[jj + 1][kk][0] == '-':
								temp[jj + 1][kk][0] = 'D'
							else:
								temp[jj + 1][kk].append('D')
						if li[pp] == 'R' and kk == c - 1:
							pass
						elif li[pp] == 'R':
							if arr[jj][kk + 1][0] == '#':
								pass
							elif temp[jj][kk + 1][0] == '-':
								temp[jj][kk + 1][0] = 'R'
							else:
								temp[jj][kk + 1].append('R')
						if li[pp] == 'L' and kk == 0:
							pass
						elif li[pp] == 'L':
							if arr[jj][kk - 1][0] == '#':
								pass
							elif temp[jj][kk - 1][0] == '-':
								temp[jj][kk - 1][0] = 'L'
							else:
								temp[jj][kk - 1].append('L')
		for i in range(r):
			for j in range(c):
				if temp[i][j][0] == '-' or temp[i][j][0] == '#':
					pass
				else:
					le = len(temp[i][j])
					cnt += le * (le - 1) // 2
				arr[i][j] = temp[i][j]
		t += 1
	print(cnt)


t = int(input())
for _ in range(t):
	(r, c) = [int(i) for i in input().split()]
	g = []
	p = []
	for _ in range(max(r, c)):
		y = []
		for _ in range(r):
			y.append([0] * c)
		p.append(y)
	for _ in range(r):
		l = input()
		g.append(l)
	for i in range(r):
		for j in range(c):
			if g[i][j] == 'U':
				for k in range(1, i + 1):
					if g[i - k][j] == '#':
						break
					else:
						p[k][i - k][j] += 1
			elif g[i][j] == 'R':
				for k in range(j + 1, c):
					if g[i][k] == '#':
						break
					else:
						p[k - j][i][k] += 1
			elif g[i][j] == 'D':
				for k in range(i + 1, r):
					if g[k][j] == '#':
						break
					else:
						p[k - i][k][j] += 1
			elif g[i][j] == 'L':
				for k in range(1, j + 1):
					if g[i][j - k] == '#':
						break
					else:
						p[k][i][j - k] += 1
	ans = 0
	for i in range(max(r, c)):
		for j in range(r):
			for k in range(c):
				ans += p[i][j][k] * (p[i][j][k] - 1) / 2
	print(int(ans))


from collections import Counter
t = int(input())
for x in range(t):
	inp = list(map(int, input().split()))
	r = inp[0]
	c = inp[1]
	listo = []
	listb = set()
	pair = 0
	for i in range(r):
		string = input()
		for j in range(len(string)):
			if string[j] == 'U':
				listo.append([i, j, 1])
			elif string[j] == 'D':
				listo.append([i, j, 2])
			elif string[j] == 'L':
				listo.append([i, j, 3])
			elif string[j] == 'R':
				listo.append([i, j, 4])
			elif string[j] == '#':
				listb.add((i, j))
	for y in range(max(r, c)):
		nants = Counter()
		for i in range(len(listo)):
			if listo[i][2] != 5:
				nants[tuple(listo[i][:-1])] += 1
		for key in nants:
			pair += nants[key] * (nants[key] - 1) // 2
		for ant in listo:
			if ant[2] == 1:
				ant[0] -= 1
			elif ant[2] == 2:
				ant[0] += 1
			elif ant[2] == 3:
				ant[1] -= 1
			elif ant[2] == 4:
				ant[1] += 1
			if tuple(ant[:-1]) in listb:
				ant[2] = 5
			elif ant[0] < 0 or ant[0] >= r:
				ant[2] = 5
			elif ant[1] < 0 or ant[1] >= c:
				ant[2] = 5
	print(pair)


from collections import Counter

def binomialCoef(n, k):
	C = [[0 for x in range(k + 1)] for x in range(n + 1)]
	for i in range(n + 1):
		for j in range(min(i, k) + 1):
			if j == 0 or j == i:
				C[i][j] = 1
			else:
				C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
	return C[n][k]
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	d = dict()
	grid = [None] * r
	for i in range(r):
		grid[i] = input()
	for i in range(r):
		for j in range(c):
			if grid[i][j] == 'U':
				kk = i
				sec = 0
				while kk >= 0:
					if grid[kk][j] == '#':
						break
					try:
						d['r' + str(kk) + 'c' + str(j)].append(sec)
					except:
						d['r' + str(kk) + 'c' + str(j)] = [sec]
					sec += 1
					kk -= 1
			if grid[i][j] == 'D':
				kk = i
				sec = 0
				while kk < r:
					if grid[kk][j] == '#':
						break
					try:
						d['r' + str(kk) + 'c' + str(j)].append(sec)
					except:
						d['r' + str(kk) + 'c' + str(j)] = [sec]
					sec += 1
					kk += 1
			if grid[i][j] == 'R':
				kk = j
				sec = 0
				while kk < c:
					if grid[i][kk] == '#':
						break
					try:
						d['r' + str(i) + 'c' + str(kk)].append(sec)
					except:
						d['r' + str(i) + 'c' + str(kk)] = [sec]
					sec += 1
					kk += 1
			if grid[i][j] == 'L':
				kk = j
				sec = 0
				while kk >= 0:
					if grid[i][kk] == '#':
						break
					try:
						d['r' + str(i) + 'c' + str(kk)].append(sec)
					except:
						d['r' + str(i) + 'c' + str(kk)] = [sec]
					sec += 1
					kk -= 1
	ans = 0
	for i in d.values():
		f = dict(Counter(i))
		for j in f.values():
			ans += binomialCoef(j, 2)
	print(ans)


def sumOfN(n):
	return n * (n - 1) // 2

def display():
	for i in range(r):
		for j in range(c):
			print(grid[i][j], end=' ')
		print()
	print()
for t in range(int(input())):
	(r, c) = map(int, input().split())
	grid = []
	pairs = 0
	for i in range(r):
		to_add = []
		for x in input().strip():
			to_add.append([x, 1])
		grid.append(to_add)
	steps = max(r, c)
	for _ in range(steps):
		for i in range(r):
			for j in range(c):
				s = grid[i][j][0][:grid[i][j][1]]
				if s == '#' or s == '-':
					continue
				for ants in s:
					if ants == 'U':
						if i > 0:
							if grid[i - 1][j][0] != '#':
								grid[i - 1][j][0] += 'U'
					elif ants == 'D':
						if i < r - 1:
							if grid[i + 1][j][0] != '#':
								grid[i + 1][j][0] += 'D'
					elif ants == 'L':
						if j > 0:
							if grid[i][j - 1][0] != '#':
								grid[i][j - 1][0] += 'L'
					elif ants == 'R':
						if j < c - 1:
							if grid[i][j + 1][0] != '#':
								grid[i][j + 1][0] += 'R'
				grid[i][j][0] = '-' if len(grid[i][j][0]) == grid[i][j][1] else grid[i][j][0][grid[i][j][1]:]
		for i in range(r):
			for j in range(c):
				if grid[i][j][0].lstrip('-') != '':
					grid[i][j][0] = grid[i][j][0].lstrip('-')
					pairs += sumOfN(len(grid[i][j][0]))
				grid[i][j][1] = len(grid[i][j][0])
	print(pairs)


def nCr(n, r):
	return fact(n) / (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res
while True:
	try:
		for _ in range(int(input())):
			(r, c) = map(int, input().split())
			arena = [[i for i in input().strip()] for j in range(r)]
			antsInitialPositions = []
			antsDirection = []
			antEaterPositions = []
			for i in range(r):
				for j in range(c):
					if arena[i][j] in ['R', 'U', 'D', 'L']:
						antsInitialPositions.append([i, j])
						antsDirection.append(arena[i][j])
					elif arena[i][j] == '#':
						antEaterPositions.append([i, j])
			antCount = len(antsInitialPositions)
			grid = [[{} for j in range(c)] for i in range(r)]
			for current in range(antCount):
				(i, j) = antsInitialPositions[current]
				direction = antsDirection[current]
				(movei, movej) = (i, j)
				if direction == 'D':
					steps = 0
					while movei < r and arena[movei][movej] != '#':
						steps = abs(i - movei)
						if steps in grid[movei][movej]:
							grid[movei][movej][steps] += 1
						else:
							grid[movei][movej][steps] = 1
						movei += 1
				elif direction == 'U':
					steps = 0
					while movei >= 0 and arena[movei][movej] != '#':
						steps = abs(i - movei)
						if steps in grid[movei][movej]:
							grid[movei][movej][steps] += 1
						else:
							grid[movei][movej][steps] = 1
						movei -= 1
				elif direction == 'L':
					steps = 0
					while movej >= 0 and arena[movei][movej] != '#':
						steps = abs(j - movej)
						if steps in grid[movei][movej]:
							grid[movei][movej][steps] += 1
						else:
							grid[movei][movej][steps] = 1
						movej -= 1
				elif direction == 'R':
					steps = 0
					while movej < c and arena[movei][movej] != '#':
						steps = abs(j - movej)
						if steps in grid[movei][movej]:
							grid[movei][movej][steps] += 1
						else:
							grid[movei][movej][steps] = 1
						movej += 1
			meetings = 0
			for i in range(r):
				for j in range(c):
					for meets in grid[i][j].values():
						if meets >= 2:
							meetings += nCr(meets, 2)
			print(int(meetings))
	except (ValueError, EOFError) as e:
		break


def func(grid, r, c):
	count = 0
	flag = 0
	for i in range(r):
		for j in range(c):
			if '#' in grid[i][j][0]:
				grid[i][j][0] = '#'
			else:
				l = len(grid[i][j][0])
				count += l * (l - 1) // 2
				x = grid[i][j][0]
				for k in x:
					flag = 1
					if k == 'U':
						if i > 0:
							grid[i - 1][j][1].append('U')
					if k == 'D':
						if i < r - 1:
							grid[i + 1][j][1].append('D')
					if k == 'L':
						if j > 0:
							grid[i][j - 1][1].append('L')
					if k == 'R':
						if j < c - 1:
							grid[i][j + 1][1].append('R')
	for i in range(r):
		for j in range(c):
			if grid[i][j][0] != '#':
				grid[i][j][0] = grid[i][j][1]
				grid[i][j][1] = []
	if flag == 0:
		return count
	else:
		return count + func(grid, r, c)
t = int(input())
for i in range(t):
	a = [int(i) for i in input().split()]
	r = a[0]
	c = a[1]
	arr = [str(input()) for i in range(r)]
	grid = [[[[j], []] for j in arr[i]] for i in range(r)]
	print(func(grid, r, c))


T = int(input())

def func(l):
	count = 0
	for i in range(len(l)):
		for j in range(len(l[i])):
			count += l[i][j].count('U') + l[i][j].count('D') + l[i][j].count('L') + l[i][j].count('R')
			if count > 1:
				return 1
	return 0
for i in range(T):
	(R, C) = map(int, input().split())
	l = []
	for j in range(R):
		p = input()
		l.append([])
		for k in range(C):
			if p[k] != '-':
				l[j].append([p[k]])
			else:
				l[j].append([])
	c = 0
	while func(l):
		l1 = []
		for j in range(len(l)):
			l1.append([])
			for k in range(len(l[j])):
				l1[j].append([])
				for x in range(len(l[j][k])):
					l1[j][k].append(l[j][k][x])
		for j in range(R):
			for k in range(C):
				f = 0
				if '#' in l[j][k]:
					l[j][k] = ['#']
					continue
				if 'U' in l[j][k]:
					f += 1
					if j - 1 >= 0:
						l1[j - 1][k].append('U*')
				if 'D' in l[j][k]:
					f += 1
					if j + 1 <= R - 1:
						l1[j + 1][k].append('D*')
				if 'L' in l[j][k]:
					f += 1
					if k - 1 >= 0:
						l1[j][k - 1].append('L*')
				if 'R' in l[j][k]:
					f += 1
					if k + 1 <= C - 1:
						l1[j][k + 1].append('R*')
				if f > 0:
					if '#' not in l[j][k]:
						c += f * (f - 1) // 2
		l = []
		for j in range(len(l1)):
			l.append([])
			for k in range(len(l1[j])):
				l[j].append([])
				for x in range(len(l1[j][k])):
					if l1[j][k][x] not in ['L', 'R', 'U', 'D']:
						l[j][k].append(l1[j][k][x][0])
	print(c)


def ncr(n, r):
	return int(fact(n) / (fact(r) * fact(n - r)))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res
t = int(input())
for _ in range(t):
	(r, c) = map(int, input().split())
	a = []
	tm = []
	for i in range(r):
		x = list(input())
		a.append(x)
	x = []
	for i in range(r):
		d = []
		for j in range(c):
			y = [0] * 50
			d.append(y)
		x.append(d)
	for i in range(r):
		for j in range(c):
			if a[i][j] == 'U':
				q = 1
				for k in range(i - 1, -1, -1):
					if a[k][j] == '#':
						break
					x[k][j][q] += 1
					q += 1
			elif a[i][j] == 'D':
				q = 1
				for k in range(i + 1, r):
					if a[k][j] == '#':
						break
					x[k][j][q] += 1
					q += 1
			elif a[i][j] == 'R':
				q = 1
				for k in range(j + 1, c):
					if a[i][k] == '#':
						break
					x[i][k][q] += 1
					q += 1
			elif a[i][j] == 'L':
				q = 1
				for k in range(j - 1, -1, -1):
					if a[i][k] == '#':
						break
					x[i][k][q] += 1
					q += 1
	ans = 0
	for i in range(r):
		for j in range(c):
			for k in range(50):
				ans += ncr(x[i][j][k], 2)
	print(ans)


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	m = [[*input()] for _ in range(r)]
	ans = 0
	p = []
	for i in range(r):
		for j in range(c):
			if m[i][j] in 'UDLR':
				p.append([i, j, m[i][j]])
	from collections import Counter
	for i in range(max(r, c) + 1):
		z = Counter([tuple(i[:2]) for i in p])
		for j in z.values():
			ans += j * (j - 1) // 2
		d = set()
		for j in range(len(p)):
			if p[j][2] == 'U':
				if p[j][0] > 0 and m[p[j][0] - 1][p[j][1]] != '#':
					p[j][0] -= 1
				else:
					d.add(j)
			elif p[j][2] == 'R':
				if p[j][1] < c - 1 and m[p[j][0]][p[j][1] + 1] != '#':
					p[j][1] += 1
				else:
					d.add(j)
			elif p[j][2] == 'L':
				if p[j][1] > 0 and m[p[j][0]][p[j][1] - 1] != '#':
					p[j][1] -= 1
				else:
					d.add(j)
			elif p[j][0] < r - 1 and m[p[j][0] + 1][p[j][1]] != '#':
				p[j][0] += 1
			else:
				d.add(j)
		p = [p[i] for i in set([*range(len(p))]) - d]
	print(ans)


def count_ants(l, r, u, d):
	cnt = 0
	if l is False:
		cnt += 1
	if r is False:
		cnt += 1
	if u is False:
		cnt += 1
	if d is False:
		cnt += 1
	return cnt

def solve(m, row, col):
	ans = 0
	for i in range(row):
		for j in range(col):
			lw = True
			rw = True
			uw = True
			dw = True
			if m[i][j] == '#':
				continue
			for d in range(1, max(row, col)):
				cnt = 0
				if j - d < 0:
					lw = False
				if j + d >= col:
					rw = False
				if i - d < 0:
					uw = False
				if i + d >= row:
					dw = False
				if count_ants(lw, rw, uw, dw) > 2:
					break
				if lw and j - d >= 0:
					if m[i][j - d] == 'R':
						cnt += 1
					elif m[i][j - d] == '#':
						lw = False
				if rw and j + d < col:
					if m[i][j + d] == 'L':
						cnt += 1
					elif m[i][j + d] == '#':
						rw = False
				if uw and i - d >= 0:
					if m[i - d][j] == 'D':
						cnt += 1
					elif m[i - d][j] == '#':
						uw = False
				if dw and i + d < row:
					if m[i + d][j] == 'U':
						cnt += 1
					elif m[i + d][j] == '#':
						dw = False
				if cnt > 1:
					ans += cnt * (cnt - 1) // 2
	return ans

def read():
	t = int(input())
	for i in range(t):
		(r, c) = list(map(int, input().strip().split()))
		m = [[] for i in range(r)]
		for i in range(r):
			s = input().strip()
			m[i] = s
		ans = solve(m, r, c)
		print(ans)
read()


t = int(input())
for i in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	ar = []
	for i in range(n):
		ar.append(input())
	arr = []
	cnt = []
	for i in range(n):
		a = []
		b = []
		for j in range(m):
			a.append({0: 0})
			b.append(0)
		cnt.append(b)
		arr.append(a)
	for i in range(n):
		for j in range(m):
			if ar[i][j] == 'U':
				c = 1
				for k in range(i - 1, -1, -1):
					if ar[k][j] == '#':
						break
					if c in arr[k][j].keys():
						cnt[k][j] = cnt[k][j] - arr[k][j][c] * (arr[k][j][c] - 1) // 2
						arr[k][j][c] += int(1)
						cnt[k][j] = cnt[k][j] + arr[k][j][c] * (arr[k][j][c] - 1) // 2
					else:
						arr[k][j][c] = int(1)
					c = c + 1
			elif ar[i][j] == 'D':
				c = 1
				for k in range(i + 1, n, 1):
					if ar[k][j] == '#':
						break
					if c in arr[k][j].keys():
						cnt[k][j] = cnt[k][j] - arr[k][j][c] * (arr[k][j][c] - 1) // 2
						arr[k][j][c] += int(1)
						cnt[k][j] = cnt[k][j] + arr[k][j][c] * (arr[k][j][c] - 1) // 2
					else:
						arr[k][j][c] = int(1)
					c = c + 1
			elif ar[i][j] == 'L':
				c = 1
				for k in range(j - 1, -1, -1):
					if ar[i][k] == '#':
						break
					if c in arr[i][k].keys():
						cnt[i][k] = cnt[i][k] - arr[i][k][c] * (arr[i][k][c] - 1) // 2
						arr[i][k][c] += int(1)
						cnt[i][k] = cnt[i][k] + arr[i][k][c] * (arr[i][k][c] - 1) // 2
					else:
						arr[i][k][c] = int(1)
					c = c + 1
			elif ar[i][j] == 'R':
				c = 1
				for k in range(j + 1, m, 1):
					if ar[i][k] == '#':
						break
					if c in arr[i][k].keys():
						cnt[i][k] = cnt[i][k] - arr[i][k][c] * (arr[i][k][c] - 1) // 2
						arr[i][k][c] += int(1)
						cnt[i][k] = cnt[i][k] + arr[i][k][c] * (arr[i][k][c] - 1) // 2
					else:
						arr[i][k][c] = int(1)
					c = c + 1
	c = 0
	for i in range(n):
		for j in range(m):
			c = c + cnt[i][j]
	print(c)


from collections import Counter
t = int(input())
for _ in range(t):
	(r, c) = list(map(int, input().split()))
	matrix = []
	for i in range(r):
		matrix.append(list(input()))
	sim = [[[] for i in range(c)] for j in range(r)]
	ants = []
	eaters = []
	for i in range(r):
		for j in range(c):
			if matrix[i][j] == 'U' or matrix[i][j] == 'D' or matrix[i][j] == 'L' or (matrix[i][j] == 'R'):
				ants.append([i, j, matrix[i][j]])
			elif matrix[i][j] == '#':
				eaters.append([i, j])
	for i in range(len(ants)):
		(row, col, d) = ants[i]
		ver = 0
		hor = 0
		if d == 'U':
			ver = -1
		elif d == 'D':
			ver = 1
		elif d == 'L':
			hor = -1
		else:
			hor = 1
		time = 0
		while row < r and row >= 0 and (col >= 0) and (col < c) and (matrix[row][col] != '#'):
			if time != 0:
				sim[row][col].append(time)
			row += ver
			col += hor
			time += 1
	ans = 0
	for i in range(r):
		for j in range(c):
			temp = Counter(sim[i][j])
			for k in temp:
				var = temp[k]
				ans += var * (var - 1) // 2
	print(ans)


import math

def findHash(x):
	value = x[0] * 100 + x[1] * 10000
	return value

def nCr(n):
	f = math.factorial
	return f(n) / f(2) / f(n - 2)
for _ in range(int(input())):
	(row, col) = map(int, input().split())
	matrix = [[None for x in range(col)] for y in range(row)]
	antU = []
	antD = []
	antL = []
	antR = []
	antEater = []
	ants = 0
	for i in range(row):
		s = input()
		for j in range(len(s)):
			if s[j] == '#':
				antEater.append([i, j])
			elif s[j] == 'U':
				antU.append([i, j])
			elif s[j] == 'D':
				antD.append([i, j])
			elif s[j] == 'L':
				antL.append([i, j])
			elif s[j] == 'R':
				antR.append([i, j])
	turns = max(row, col)
	for i in range(turns):
		d = {}
		x = 0
		while x < len(antU):
			if antU[x][0] - 1 < 0:
				antU.pop(x)
			else:
				antU[x][0] -= 1
				if antU[x] in antEater:
					antU.pop(x)
				else:
					hashValue = findHash(antU[x])
					if hashValue in d:
						d[hashValue] += 1
					else:
						d[hashValue] = 1
					x += 1
		x = 0
		while x < len(antD):
			if antD[x][0] + 1 >= row:
				antD.pop(x)
			else:
				antD[x][0] += 1
				if antD[x] in antEater:
					antD.pop(x)
				else:
					hashValue = findHash(antD[x])
					if hashValue in d:
						d[hashValue] += 1
					else:
						d[hashValue] = 1
					x += 1
		x = 0
		while x < len(antR):
			if antR[x][1] + 1 >= col:
				antR.pop(x)
			else:
				antR[x][1] += 1
				if antR[x] in antEater:
					antR.pop(x)
				else:
					hashValue = findHash(antR[x])
					if hashValue in d:
						d[hashValue] += 1
					else:
						d[hashValue] = 1
					x += 1
		x = 0
		while x < len(antL):
			if antL[x][1] - 1 < 0:
				antL.pop(x)
			else:
				antL[x][1] -= 1
				if antL[x] in antEater:
					antL.pop(x)
				else:
					hashValue = findHash(antL[x])
					if hashValue in d:
						d[hashValue] += 1
					else:
						d[hashValue] = 1
					x += 1
		for x in d:
			if d[x] > 1:
				ants += int(nCr(d[x]))
	print(ants)


for _ in range(int(input())):
	(r, c) = [int(i) for i in input().split()]
	zone = [[0 for x in range(c)] for y in range(r)]
	ants = []
	for i in range(r):
		s = input()
		for w in range(len(s)):
			if s[w] == '#':
				zone[i][w] = 1
			elif s[w] in ['R', 'U', 'L', 'D']:
				ants.append([1, i, w, s[w]])
	(pairs, x, y) = (0, 2, 1)
	for time in range(max(r, c)):
		for a in ants:
			if a[3] is 'U':
				a[y] -= 1
			elif a[3] == 'D':
				a[y] += 1
			elif a[3] == 'L':
				a[x] -= 1
			else:
				a[x] += 1
			if a[x] < 0 or a[x] >= c:
				a[0] = 0
			elif a[y] < 0 or a[y] >= r:
				a[0] = 0
			elif zone[a[y]][a[x]] == 1:
				a[0] = 0
		ants.sort(key=lambda val: (val[0], val[1], val[2]))
		for i in range(len(ants)):
			if ants[i][0] == 1:
				break
		ants = ants[i:]
		if len(ants) == 0:
			break
		prev = [ants[0][1], ants[0][2]]
		cur_num = 1
		for a in ants[1:]:
			if prev[0] == a[1] and prev[1] == a[2]:
				cur_num += 1
			else:
				pairs += cur_num * (cur_num - 1) // 2
				cur_num = 1
				prev[0] = a[1]
				prev[1] = a[2]
		pairs += cur_num * (cur_num - 1) // 2
	print(pairs)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		s = input()
		arr.append(list(s))
	ans = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j] != '#':
				P = []
				Q = []
				R = []
				S = []
				r = i
				c = j
				d = 0
				while c >= 0 and arr[r][c] != '#':
					if arr[r][c] == 'R':
						P.append(d)
					c = c - 1
					d += 1
				r = i
				c = j
				d = 0
				while c < m and arr[r][c] != '#':
					if arr[r][c] == 'L':
						Q.append(d)
					c = c + 1
					d += 1
				r = i
				c = j
				d = 0
				while r >= 0 and arr[r][c] != '#':
					if arr[r][c] == 'D':
						R.append(d)
					r = r - 1
					d += 1
				r = i
				c = j
				d = 0
				while r < n and arr[r][c] != '#':
					if arr[r][c] == 'U':
						S.append(d)
					r = r + 1
					d += 1
				for e in P:
					if e in Q:
						ans += 1
				for e in P:
					if e in R:
						ans += 1
				for e in P:
					if e in S:
						ans += 1
				for e in Q:
					if e in R:
						ans += 1
				for e in Q:
					if e in S:
						ans += 1
				for e in R:
					if e in S:
						ans += 1
	print(ans)


t = int(input())
for p in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append([])
		for j in range(m):
			arr[i].append({})
	ar = []
	for q in range(n):
		a = input()
		a = list(a)
		ar.append(a)
	count = 0
	for i in range(n):
		for j in range(m):
			k = j
			while k >= 0:
				if ar[i][k] == 'R':
					if j - k not in arr[i][j]:
						arr[i][j][j - k] = 1
					else:
						arr[i][j][j - k] += 1
				elif ar[i][k] == '#':
					break
				k -= 1
			k = j
			while k < m:
				if ar[i][k] == 'L':
					if k - j not in arr[i][j]:
						arr[i][j][k - j] = 1
					else:
						arr[i][j][k - j] += 1
				elif ar[i][k] == '#':
					break
				k += 1
			k = i
			while k < n:
				if ar[k][j] == 'U':
					if k - i not in arr[i][j]:
						arr[i][j][k - i] = 1
					else:
						arr[i][j][k - i] += 1
				elif ar[k][j] == '#':
					break
				k += 1
			k = i
			while k >= 0:
				if ar[k][j] == 'D':
					if i - k not in arr[i][j]:
						arr[i][j][i - k] = 1
					else:
						arr[i][j][i - k] += 1
				elif ar[k][j] == '#':
					break
				k -= 1
	count = 0
	for i in range(n):
		for j in range(m):
			for d in arr[i][j]:
				if arr[i][j][d] == 2:
					count += 1
				else:
					count += arr[i][j][d] * (arr[i][j][d] - 1) // 2
	print(count)


t = int(input())
for i in range(t):
	(r, c) = map(int, input().rstrip().split())
	arr = []
	for j in range(r):
		arr.append(input().rstrip())
	n = max(r, c)
	lst = [0 for j in range(n)]
	full_list = []
	for j in range(r):
		te = []
		for k in range(c):
			te.append(lst.copy())
		full_list.append(te)
	for j in range(r):
		for k in range(c):
			if arr[j][k] == 'R':
				l = 1
				for rj in range(k + 1, c):
					if arr[j][rj] == '#':
						break
					full_list[j][rj][l] = full_list[j][rj][l] + 1
					l = l + 1
			elif arr[j][k] == 'L':
				l = 1
				for rj in range(k - 1, -1, -1):
					if arr[j][rj] == '#':
						break
					full_list[j][rj][l] += 1
					l = l + 1
			elif arr[j][k] == 'D':
				l = 1
				for rj in range(j + 1, r):
					if arr[rj][k] == '#':
						break
					full_list[rj][k][l] += 1
					l = l + 1
			elif arr[j][k] == 'U':
				l = 1
				for rj in range(j - 1, -1, -1):
					if arr[rj][k] == '#':
						break
					full_list[rj][k][l] += 1
					l = l + 1
	co = 0
	for j in range(r):
		for k in range(c):
			for rj in range(n):
				if full_list[j][k][rj] == 2:
					co = co + 1
				elif full_list[j][k][rj] == 3:
					co = co + 3
				elif full_list[j][k][rj] == 4:
					co = co + 6
	print(co)


import sys
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = []
	for i in range(n):
		s.append(input())
	ans = []
	for i in range(n):
		ans.append([])
		for j in range(m):
			ans[i].append([])
	for i in range(n):
		for j in range(m):
			c = 0
			if s[i][j] == 'U':
				for k in range(i, -1, -1):
					if s[k][j] == '#':
						break
					ans[k][j].append(c)
					c += 1
			elif s[i][j] == 'D':
				for k in range(i, n):
					if s[k][j] == '#':
						break
					ans[k][j].append(c)
					c += 1
			elif s[i][j] == 'L':
				for k in range(j, -1, -1):
					if s[i][k] == '#':
						break
					ans[i][k].append(c)
					c += 1
			elif s[i][j] == 'R':
				for k in range(j, m):
					if s[i][k] == '#':
						break
					ans[i][k].append(c)
					c += 1
	for i in range(n):
		for j in range(m):
			ans[i][j].sort()
	res = []
	for i in range(n):
		for j in range(m):
			c = 1
			for k in range(1, len(ans[i][j])):
				if ans[i][j][k] == ans[i][j][k - 1]:
					c += 1
				else:
					if c != 1:
						res.append(c)
					c = 1
				if k == len(ans[i][j]) - 1:
					if c != 1:
						res.append(c)
	pairs = 0
	for i in range(len(res)):
		pairs += res[i] * (res[i] - 1) // 2
	print(pairs)


for t in range(int(input())):
	(r, c) = list(map(int, input().split()))
	deadzone = [[0 for x in range(c)] for y in range(r)]
	ants = []
	for q in range(r):
		s = input()
		for w in range(len(s)):
			if s[w] == '#':
				deadzone[q][w] = 1
			elif s[w] in ('U', 'D', 'L', 'R'):
				ants.append([1, q, w, s[w]])
	pairs = 0
	x = 2
	y = 1
	for time in range(max(r, c)):
		for a in ants:
			if a[3] == 'U':
				a[y] -= 1
			elif a[3] == 'D':
				a[y] += 1
			elif a[3] == 'L':
				a[x] -= 1
			else:
				a[x] += 1
			if a[x] < 0 or a[x] >= c:
				a[0] = 0
			elif a[y] < 0 or a[y] >= r:
				a[0] = 0
			elif deadzone[a[y]][a[x]] == 1:
				a[0] = 0
		ants.sort(key=lambda val: (val[0], val[1], val[2]))
		for i in range(len(ants)):
			if ants[i][0] == 1:
				break
		ants = ants[i:]
		if len(ants) == 0:
			break
		prev = [ants[0][1], ants[0][2]]
		cur_num = 1
		for a in ants[1:]:
			if prev[0] == a[1] and prev[1] == a[2]:
				cur_num += 1
			else:
				pairs += cur_num * (cur_num - 1) // 2
				cur_num = 1
				prev[0] = a[1]
				prev[1] = a[2]
		pairs += cur_num * (cur_num - 1) // 2
	print(pairs)


test = int(input())
for _ in range(test):
	(R, C) = list(map(int, input().split()))
	grid = []
	R_list = []
	L_list = []
	U_list = []
	D_list = []
	pairs = 0
	for i in range(R):
		row = list(input())
		R_list.append(list((i for (i, value) in enumerate(row) if value == 'R')))
		L_list.append(list((i for (i, value) in enumerate(row) if value == 'L')))
		U_list.append(list((i for (i, value) in enumerate(row) if value == 'U')))
		D_list.append(list((i for (i, value) in enumerate(row) if value == 'D')))
		grid.append(row)
	for i in range(max(R, C)):
		for j in range(len(R_list)):
			for x in range(len(R_list[j])):
				if R_list[j][x] + 1 >= C:
					R_list[j][x] = '-'
				elif grid[j][R_list[j][x] + 1] == '#':
					R_list[j][x] = '-'
				else:
					R_list[j][x] = R_list[j][x] + 1
			R_list[j] = list(filter('-'.__ne__, R_list[j]))
		for j in range(len(L_list)):
			for x in range(len(L_list[j])):
				if L_list[j][x] - 1 < 0:
					L_list[j][x] = '-'
				elif grid[j][L_list[j][x] - 1] == '#':
					L_list[j][x] = '-'
				else:
					L_list[j][x] = L_list[j][x] - 1
			L_list[j] = list(filter('-'.__ne__, L_list[j]))
		for j in range(len(U_list)):
			for x in range(len(U_list[j])):
				if j == 0:
					U_list[j][x] = '-'
				elif grid[j - 1][U_list[j][x]] == '#':
					U_list[j][x] = '-'
				else:
					U_list[j - 1].append(U_list[j][x])
					U_list[j][x] = '-'
			U_list[j] = list(filter('-'.__ne__, U_list[j]))
		for j in range(len(D_list)):
			for x in range(len(D_list[j])):
				if isinstance(D_list[j][x], str):
					continue
				if j == R - 1:
					D_list[j][x] = '-'
				elif grid[j + 1][D_list[j][x]] == '#':
					D_list[j][x] = '-'
				else:
					D_list[j + 1].append(str(D_list[j][x]))
					D_list[j][x] = '-'
			D_list[j] = list(filter('-'.__ne__, D_list[j]))
		for k in range(R):
			D_list[k] = list(map(int, D_list[k]))
		for k in range(R):
			if len(R_list[k]) != 0 and len(L_list[k]) != 0:
				s1 = set(R_list[k])
				s2 = set(L_list[k])
				set1 = s1.intersection(s2)
				pairs += len(list(set1))
			if len(R_list[k]) != 0 and len(D_list[k]) != 0:
				s1 = set(R_list[k])
				s2 = set(D_list[k])
				set1 = s1.intersection(s2)
				pairs += len(list(set1))
			if len(R_list[k]) != 0 and len(U_list[k]) != 0:
				s1 = set(R_list[k])
				s2 = set(U_list[k])
				set1 = s1.intersection(s2)
				pairs += len(list(set1))
			if len(L_list[k]) != 0 and len(D_list[k]) != 0:
				s1 = set(L_list[k])
				s2 = set(D_list[k])
				set1 = s1.intersection(s2)
				pairs += len(list(set1))
			if len(L_list[k]) != 0 and len(U_list[k]) != 0:
				s1 = set(L_list[k])
				s2 = set(U_list[k])
				set1 = s1.intersection(s2)
				pairs += len(list(set1))
			if len(U_list[k]) != 0 and len(D_list[k]) != 0:
				s1 = set(U_list[k])
				s2 = set(D_list[k])
				set1 = s1.intersection(s2)
				pairs += len(list(set1))
	print(pairs)


from collections import deque, defaultdict
t = int(input())

def f(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)
for _ in range(t):
	(R, C) = map(int, input().strip().split())
	arr = []
	ants = deque([])
	pos = defaultdict(lambda : 0)
	for i in range(R):
		s = input().strip()
		S = []
		for j in range(C):
			S.append(s[j])
			if s[j].isalpha():
				ants.append((i, j, s[j], 0))
		arr.append(S)
	pairs = 0
	ptime = 0
	ppp = set()
	while ants != deque([]):
		(i, j, d, t) = ants.popleft()
		if t == ptime + 1:
			ptime = t
			for p in ppp:
				pairs += f(pos[p], 2)
			pos.clear()
			ppp.clear()
		if d == 'U':
			if i == 0:
				pass
			elif arr[i - 1][j] == '#':
				pass
			else:
				pos[i - 1, j] += 1
				ants.append((i - 1, j, 'U', t + 1))
				if pos[i - 1, j] % 2 == 0:
					ppp.add((i - 1, j))
		elif d == 'D':
			if i == R - 1:
				pass
			elif arr[i + 1][j] == '#':
				pass
			else:
				pos[i + 1, j] += 1
				ants.append((i + 1, j, 'D', t + 1))
				if pos[i + 1, j] % 2 == 0:
					ppp.add((i + 1, j))
		elif d == 'R':
			if j == C - 1:
				pass
			elif arr[i][j + 1] == '#':
				pass
			else:
				pos[i, j + 1] += 1
				ants.append((i, j + 1, 'R', t + 1))
				if pos[i, j + 1] % 2 == 0:
					ppp.add((i, j + 1))
		elif j == 0:
			pass
		elif arr[i][j - 1] == '#':
			pass
		else:
			pos[i, j - 1] += 1
			ants.append((i, j - 1, 'L', t + 1))
			if pos[i, j - 1] % 2 == 0:
				ppp.add((i, j - 1))
	print(pairs)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = [[[] for i in range(b)] for i in range(a)]
	d = [input() for i in range(a)]
	for i in range(a):
		for j in range(b):
			if d[i][j] == 'R':
				k = 1
				for m in range(j + 1, b):
					if d[i][m] != '#':
						c[i][m].append(k)
						k += 1
					else:
						break
			elif d[i][j] == 'L':
				k = 1
				for m in range(j - 1, -1, -1):
					if d[i][m] != '#':
						c[i][m].append(k)
						k += 1
					else:
						break
			elif d[i][j] == 'U':
				k = 1
				for m in range(i - 1, -1, -1):
					if d[m][j] != '#':
						c[m][j].append(k)
						k += 1
					else:
						break
			elif d[i][j] == 'D':
				k = 1
				for m in range(i + 1, a):
					if d[m][j] != '#':
						c[m][j].append(k)
						k += 1
					else:
						break
	ans = 0
	for i in c:
		if len(i) != 0:
			for j in i:
				k = set(j)
				for ll in k:
					ff = j.count(ll)
					if ff > 1:
						ans += math.factorial(ff) // (2 * math.factorial(ff - 2))
	print(ans)


from collections import defaultdict
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = []
	for j in range(n):
		a = list(input())
		l.append(a)
	values = [[defaultdict(int) for i in range(m)] for j in range(n)]
	for j in range(n):
		for k in range(m):
			if l[j][k] == '-' or l[j][k] == '#':
				continue
			elif l[j][k] == 'R':
				time = 1
				for x in range(k, m):
					if l[j][x] == '#':
						break
					else:
						values[j][x][time] += 1
						time += 1
			elif l[j][k] == 'L':
				time = 1
				for x in range(k, -1, -1):
					if l[j][x] == '#':
						break
					else:
						values[j][x][time] += 1
						time += 1
			elif l[j][k] == 'D':
				time = 1
				for x in range(j, n):
					if l[x][k] == '#':
						break
					else:
						values[x][k][time] += 1
						time += 1
			else:
				time = 1
				for x in range(j, -1, -1):
					if l[x][k] == '#':
						break
					else:
						values[x][k][time] += 1
						time += 1
	total = 0
	for j in range(n):
		for k in range(m):
			for x in values[j][k]:
				value = values[j][k][x]
				total += value * (value - 1) // 2
	print(total)


M = 10 ** 9 + 7
R = lambda : map(int, input().split())
for _ in range(int(input())):
	(r, c) = R()
	L = []
	for i in range(r):
		L.append([j for j in input()])
	p = 1
	ans = 0
	while p < max(r, c):
		a = [[0 for i in range(c)] for j in range(r)]
		for i in range(r):
			for j in range(c):
				if L[i][j] == '-' or L[i][j] == '#':
					continue
				else:
					if L[i][j] == 'R':
						if j + p < c:
							if L[i][j + p] == '#':
								L[i][j] = '-'
							else:
								a[i][j + p] += 1
					elif L[i][j] == 'L':
						if j - p >= 0:
							if L[i][j - p] == '#':
								L[i][j] = '-'
							else:
								a[i][j - p] += 1
					if L[i][j] == 'U':
						if i - p >= 0:
							if L[i - p][j] == '#':
								L[i][j] = '-'
							else:
								a[i - p][j] += 1
					if L[i][j] == 'D':
						if i + p < r:
							if L[i + p][j] == '#':
								L[i][j] = '-'
							else:
								a[i + p][j] += 1
		for i in range(r):
			for j in range(c):
				t1 = a[i][j]
				ans += t1 * (t1 - 1) // 2
		p += 1
	print(ans)


n = int(input())
for x in range(n):
	ant_eater = {}
	arr = []
	sam = {}
	(a, b) = list(map(int, input().split()))
	for y in range(a):
		kam = input()
		arr.append(kam)
	row = 0
	for item in arr:
		for z in range(b):
			if item[z] == '#':
				lam = str(row) + ' ' + str(z)
				ant_eater[lam] = '#'
			else:
				pass
		row += 1
	row = 0
	count = 0
	for item in arr:
		for z in range(b):
			step = 0
			if item[z] == 'U':
				jim = row
				while 6 == 6:
					if jim < 0:
						break
					lam = str(jim) + ' ' + str(z)
					if lam in ant_eater:
						break
					else:
						ham = str(jim) + ' ' + str(z) + ' ' + str(step)
						if ham in sam:
							sam[ham] += 1
						else:
							sam[ham] = 1
					jim -= 1
					step += 1
			elif item[z] == 'D':
				jim = row
				while 6 == 6:
					if jim > a - 1:
						break
					lam = str(jim) + ' ' + str(z)
					if lam in ant_eater:
						break
					else:
						ham = str(jim) + ' ' + str(z) + ' ' + str(step)
						if ham in sam:
							sam[ham] += 1
						else:
							sam[ham] = 1
					jim += 1
					step += 1
			if item[z] == 'L':
				jim = z
				while 6 == 6:
					if jim < 0:
						break
					lam = str(row) + ' ' + str(jim)
					if lam in ant_eater:
						break
					else:
						ham = str(row) + ' ' + str(jim) + ' ' + str(step)
						if ham in sam:
							sam[ham] += 1
						else:
							sam[ham] = 1
					jim -= 1
					step += 1
			if item[z] == 'R':
				jim = z
				while 6 == 6:
					if jim > b - 1:
						break
					lam = str(row) + ' ' + str(jim)
					if lam in ant_eater:
						break
					else:
						ham = str(row) + ' ' + str(jim) + ' ' + str(step)
						if ham in sam:
							sam[ham] += 1
						else:
							sam[ham] = 1
					jim += 1
					step += 1
		row += 1
	count = 0
	for item in sam:
		if sam[item] > 1:
			kk = sam[item] - 1
			count += int(kk * (kk + 1) // 2)
	print(count)


import numpy
for t in range(int(input())):
	(r, c) = map(int, input().split())
	temp = max(r, c)
	ANTS = []
	ants = numpy.zeros((r, c))
	eater = numpy.full((r, c), False)
	for row in range(r):
		cols = input()
		for col in range(c):
			if cols[col] == 'U':
				ANTS.append([row, col, -1, 0])
				ants[row][col] = 1
			elif cols[col] == 'D':
				ANTS.append([row, col, 1, 0])
				ants[row][col] = 1
			elif cols[col] == 'L':
				ANTS.append([row, col, 0, -1])
				ants[row][col] = 1
			elif cols[col] == 'R':
				ANTS.append([row, col, 0, 1])
				ants[row][col] = 1
			elif cols[col] == '#':
				eater[row][col] = True
	num = len(ANTS)
	count = 0
	for i in range(1, temp):
		j = 0
		while j < num:
			ANT = ANTS[j]
			ants[ANT[0]][ANT[1]] -= 1
			ANT[0] += ANT[2]
			ANT[1] += ANT[3]
			if ANT[0] >= r or ANT[0] < 0 or ANT[1] >= c or (ANT[1] < 0):
				ANTS.pop(j)
				j -= 1
				num -= 1
			elif eater[ANT[0]][ANT[1]] == True:
				ANTS.pop(j)
				j -= 1
				num -= 1
			else:
				ants[ANT[0]][ANT[1]] += 1
			j += 1
		flag = 0
		for x in range(r):
			for y in range(c):
				temp = ants[x][y]
				count += temp * (temp - 1) // 2
	print(int(count))


t = int(input())
for i in range(0, t):
	a = input()
	a = list(map(int, a.split()))
	r = a[0]
	c = a[1]
	grid = []
	for j in range(0, r):
		column = input()
		row_list = []
		for k in range(0, c):
			row_list.append(column[k])
		grid.append(row_list)
	meet = 0
	for j in range(0, r):
		numR = 0
		for k in range(0, c, 2):
			if grid[j][k] == 'R':
				numR += 1
			if grid[j][k] == 'L':
				meet += numR
			if grid[j][k] == '#':
				numR = 0
			if k + 1 < c and grid[j][k + 1] == '#':
				numR = 0
		numR = 0
		for k in range(1, c, 2):
			if grid[j][k] == 'R':
				numR += 1
			if grid[j][k] == 'L':
				meet += numR
			if grid[j][k] == '#':
				numR = 0
			if k + 1 < c and grid[j][k + 1] == '#':
				numR = 0
	for j in range(0, c):
		numD = 0
		for k in range(0, r, 2):
			if grid[k][j] == 'D':
				numD += 1
			if grid[k][j] == '#':
				numD = 0
			if grid[k][j] == 'U':
				meet += numD
			if k + 1 < r and grid[k + 1][j] == '#':
				numD = 0
		numD = 0
		for k in range(1, r, 2):
			if grid[k][j] == 'D':
				numD += 1
			if grid[k][j] == '#':
				numD = 0
			if grid[k][j] == 'U':
				meet += numD
			if k + 1 < r and grid[k + 1][j] == '#':
				numD = 0
	for row in range(0, r):
		for col in range(0, c):
			if grid[row][col] == 'U':
				for k in range(1, row + 1):
					if grid[row - k][col] == '#':
						break
					if col - k >= 0 and grid[row - k][col - k] == 'R':
						eaten = False
						for l in range(col - k + 1, col):
							if grid[row - k][l] == '#':
								eaten = True
								break
						if not eaten:
							meet += 1
					if col + k < c and grid[row - k][col + k] == 'L':
						eaten = False
						for l in range(col + 1, col + k):
							if grid[row - k][l] == '#':
								eaten = True
								break
						if not eaten:
							meet += 1
			if grid[row][col] == 'D':
				for k in range(1, r - row):
					if grid[row + k][col] == '#':
						break
					if col - k >= 0 and grid[row + k][col - k] == 'R':
						eaten = False
						for l in range(col - k + 1, col):
							if grid[row + k][l] == '#':
								eaten = True
								break
						if not eaten:
							meet += 1
					if col + k < c and grid[row + k][col + k] == 'L':
						eaten = False
						for l in range(col + 1, col + k):
							if grid[row + k][l] == '#':
								eaten = True
								break
						if not eaten:
							meet += 1
	print(meet)