Calvin the robot lies in an infinite rectangular grid. Calvin's source code contains a list of n commands, each either 'U', 'R', 'D', or 'L' — instructions to move a single square up, right, down, or left, respectively. How many ways can Calvin execute a non-empty contiguous substrings of commands and return to the same square he starts in? Two substrings are considered different if they have different starting or ending indices.


-----Input-----

The first line of the input contains a single positive integer, n (1 ≤ n ≤ 200) — the number of commands.

The next line contains n characters, each either 'U', 'R', 'D', or 'L' — Calvin's source code.


-----Output-----

Print a single integer — the number of contiguous substrings that Calvin can execute and return to his starting square.


-----Examples-----
Input
6
URLLDR

Output
2

Input
4
DLUU

Output
0

Input
7
RLRLRLR

Output
12



-----Note-----

In the first case, the entire source code works, as well as the "RL" substring in the second and third characters.

Note that, in the third case, the substring "LR" appears three times, and is therefore counted three times to the total result.

Source: codeforces | Difficulty: EASY
Tags: Implementation

Complete search


Solutions:
import re, sys, string, operator, functools, fractions, collections
sys.setrecursionlimit(10 ** 7)
dX = [-1, 1, 0, 0, -1, 1, -1, 1]
dY = [0, 0, -1, 1, 1, -1, -1, 1]
RI = lambda x=' ': list(map(int, input().split(x)))
RS = lambda x=' ': input().rstrip().split(x)
mod = int(1000000000.0 + 7)
eps = 1e-06
n = RI()[0]
s = RS()[0]
ans = 0
for i in range(n):
	(x, y) = (0, 0)
	for j in range(i, n):
		if s[j] == 'L':
			x -= 1
		elif s[j] == 'R':
			x += 1
		elif s[j] == 'U':
			y += 1
		else:
			y -= 1
		if x == 0 and y == 0:
			ans += 1
print(ans)


C = lambda x, y: x.count(y)

def P(s):
	return C(s, 'R') - C(s, 'L') + 1j * (C(s, 'U') - C(s, 'D'))
n = int(input())
s = input()
c = 0
for z in range(0, n):
	for l in range(z + 1, n + 1):
		c += P(s[z:l]) == 0
print(c)


n = int(input())
ch = input()
tot = 0
for i in range(len(ch) - 1):
	for j in range(i + 1, len(ch)):
		s = ch[i:j + 1]
		pos = [0, 0]
		for x in s:
			if x == 'R':
				pos[0] += 1
			if x == 'L':
				pos[0] += -1
			if x == 'U':
				pos[1] += 1
			if x == 'D':
				pos[1] += -1
		if pos[0] == 0 and pos[1] == 0:
			tot += 1
print(tot)


n = int(input())
s = input()
(a, b) = (0, 0)
E = [[0, 0]]
times = [1]
for i in range(n):
	if s[i] == 'U':
		b += 1
	elif s[i] == 'R':
		a += 1
	elif s[i] == 'D':
		b -= 1
	else:
		a -= 1
	if [a, b] not in E:
		E.append([a, b])
		times.append(1)
	else:
		times[E.index([a, b])] += 1
c = 0
for i in times:
	c += i * (i - 1) // 2
print(c)


from itertools import accumulate
n = int(input())
S = {'D': (0, -1), 'U': (0, 1), 'R': (1, 0), 'L': (-1, 0)}
line = [S[c] for c in input()]
prefix_x = list(accumulate([0] + line, lambda p, q: p + q[0]))
prefix_y = list(accumulate([0] + line, lambda p, q: p + q[1]))
ans = 0
for i in range(n + 1):
	for j in range(i + 1, n + 1):
		if prefix_x[j] == prefix_x[i] and prefix_y[j] == prefix_y[i]:
			ans += 1
print(ans)


tam = int(input())
string = input()
total = 0
substrings = [string[i:j] for i in range(len(string)) for j in range(i + 1, len(string) + 1)]
multiplas = []
for sub in substrings:
	if len(sub) % 2 == 0:
		multiplas.append(sub)
for palavra in multiplas:
	countD = 0
	countU = 0
	countR = 0
	countL = 0
	for letra in palavra:
		if letra == 'D':
			countD += 1
		elif letra == 'U':
			countU += 1
		elif letra == 'R':
			countR += 1
		elif letra == 'L':
			countL += 1
	if countD == countU and countL == countR:
		total += 1
print(total)


n = int(input())
s = input()

def abeja(x):
	a = [0, 0]
	for i in range(len(x)):
		if x[i] == 'D':
			a[1] -= 1
		elif x[i] == 'U':
			a[1] += 1
		elif x[i] == 'L':
			a[0] -= 1
		elif x[i] == 'R':
			a[0] += 1
	if a[0] == 0 and a[1] == 0:
		return True
	else:
		return False
counter = 0
k = []
for x in range(len(s) + 1):
	for y in range(len(s) + 1):
		if x < y:
			if abeja(s[x:y]) == True and (y, x) not in k:
				counter += 1
		else:
			pass
print(counter)


import collections

def search(array, pos):
	count = {'U': 0, 'D': 0, 'L': 0, 'R': 0}
	num = 0
	for x in array[pos:]:
		count[x] += 1
		if count['U'] == count['D'] and count['L'] == count['R']:
			num += 1
	return num

def main():
	move = int(input())
	cmd = input()
	count = collections.Counter(cmd)
	num = 0
	for x in range(move):
		num += search(cmd, x)
	print(num)
main()


n = int(input())
s = input()
sum = 0
for i in range(n):
	for j in range(i + 1, n + 1):
		if s[i:j].count('L') == s[i:j].count('R') and s[i:j].count('U') == s[i:j].count('D'):
			sum += 1
print(sum)


n = int(input())
a = input()
count = 0
coor = [0, 0]
for i in range(n):
	for j in range(i, n):
		coor = [0, 0]
		for x in range(i, j + 1):
			if a[x] == 'U':
				coor[1] += 1
			elif a[x] == 'D':
				coor[1] -= 1
			elif a[x] == 'R':
				coor[0] += 1
			else:
				coor[0] -= 1
		if coor == [0, 0]:
			count += 1
print(count)


def calc(s):
	c = 0
	x = 0
	y = 0
	for b in s:
		if b == 'U':
			y -= 1
		if b == 'D':
			y += 1
		if b == 'L':
			x -= 1
		if b == 'R':
			x += 1
		if x == 0 and y == 0:
			c += 1
	return c
n = input()
s = input()
cnt = 0
while s:
	cnt += calc(s)
	s = s[1:]
print(cnt)


n = int(input())
ch = input()
S = 0
for j in range(len(ch)):
	ch1 = ch[j:len(ch)]
	V = 0
	H = 0
	for i in ch1:
		if i == 'U':
			V = V + 1
		if i == 'D':
			V = V - 1
		if i == 'L':
			H = H + 1
		if i == 'R':
			H = H - 1
		if V == 0 and H == 0:
			S = S + 1
print(S)


ans = 0
a = {'U': 0, 'D': 0, 'R': 0, 'L': 0}
n = int(input())
s = input()
for i in range(n - 1):
	j = 2
	while j + i <= n:
		for k in s[i:i + j]:
			a[k] += 1
		if a['U'] == a['D'] and a['L'] == a['R']:
			ans += 1
		a['U'] = a['D'] = a['L'] = a['R'] = 0
		j += 2
print(ans)


n = int(input())
s = input()
ans = 0
for i in range(n):
	for j in range(i + 2, n + 1):
		t = s[i:j]
		if t.count('U') == t.count('D') and t.count('R') == t.count('L'):
			ans += 1
print(ans)


def f(i, j):
	subs = s[i:j + 1]
	return subs.count('L') == subs.count('R') and subs.count('U') == subs.count('D')
n = int(input())
s = input()
r = 0
for i in range(n):
	for j in range(i + 1, n):
		if f(i, j):
			r += 1
print(r)


def check(st):
	cnt = [st.count(ch) for ch in 'UDRL']
	return cnt[0] == cnt[1] and cnt[2] == cnt[3]
n = int(input())
s = input().strip()
ans = int(0)
for l in range(2, n + 1):
	for i in range(0, n - l + 1):
		if check(s[i:i + l]):
			ans += 1
print(ans)


def check(r, l, u, d):
	if r == l and u == d:
		return 1
	else:
		return 0
n = int(input())
s = list(input())
r = 0
u = 0
d = 0
l = 0
count = 0
for i in range(n):
	(u, d, l, r) = (0, 0, 0, 0)
	if s[i] == 'U':
		u += 1
	elif s[i] == 'R':
		r += 1
	elif s[i] == 'L':
		l += 1
	else:
		d += 1
	for j in range(i + 1, n):
		if s[j] == 'U':
			u += 1
		elif s[j] == 'R':
			r += 1
		elif s[j] == 'L':
			l += 1
		else:
			d += 1
		if check(r, l, u, d):
			count += 1
print(count)


def main():
	n = int(input())
	s = input()
	print(solver(s))

def solver(s):
	count = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			if substring(s[i:j]):
				count += 1
	return count

def substring(s):
	horizontal = 0
	vertical = 0
	for c in s:
		if c == 'U':
			vertical += 1
		elif c == 'D':
			vertical -= 1
		elif c == 'L':
			horizontal -= 1
		elif c == 'R':
			horizontal += 1
	return horizontal == 0 and vertical == 0
main()


def main():
	n = int(input())
	s = input()
	cnt = 0
	for i in range(n):
		vert = horiz = 0
		for j in range(i, n):
			if s[j] == 'U':
				vert += 1
			elif s[j] == 'R':
				horiz += 1
			elif s[j] == 'D':
				vert -= 1
			else:
				horiz -= 1
			if vert == 0 and horiz == 0:
				cnt += 1
	print(cnt)
main()


n = int(input())
inst = input()
dir_ = dict(U=(0, 1), D=(0, -1), L=(-1, 0), R=(1, 0))
ct = 0
for i in range(n):
	(x, y) = (0, 0)
	for j in range(i, n):
		(dx, dy) = dir_[inst[j]]
		x += dx
		y += dy
		ct += x == 0 and y == 0
print(ct)


n = int(input())
s = input()
i = 0
ans = 0
while i < n:
	(r, l, u, d) = (0, 0, 0, 0)
	g = i
	while g < n:
		if s[g] == 'R':
			r += 1
		elif s[g] == 'L':
			l += 1
		elif s[g] == 'U':
			u += 1
		elif s[g] == 'D':
			d += 1
		if d == u and l == r:
			ans += 1
		g += 1
	i += 1
print(ans)


n = int(input())
d = [(0, 0)]
for c in input():
	dpos = {'L': (-1, 0), 'R': (1, 0), 'U': (0, 1), 'D': (0, -1)}[c]
	d.append((d[-1][0] + dpos[0], d[-1][1] + dpos[1]))
print(sum((1 for i in range(n) for j in range(i + 1, n + 1) if d[i] == d[j])))


n = int(input())
s = ' ' + input()
r = [(0, 0)]
for i in range(1, n + 1):
	(x, y) = r[i - 1]
	if s[i] == 'U':
		y += 1
	if s[i] == 'D':
		y -= 1
	if s[i] == 'L':
		x -= 1
	if s[i] == 'R':
		x += 1
	r += [(x, y)]
ans = 0
for i in range(1, n):
	for j in range(i + 1, n + 1):
		if (0, 0) == (r[j][0] - r[i - 1][0], r[j][1] - r[i - 1][1]):
			ans += 1
print(ans)


n = int(input())
s = input()
(i, e) = (0, 0)
while i < n:
	k = i + 1
	while k <= n:
		(c, d) = (0, 0)
		for j in range(i, k):
			if s[j] == 'U':
				c += 1
			elif s[j] == 'D':
				c -= 1
			elif s[j] == 'R':
				d += 1
			else:
				d -= 1
		if c == 0 and d == 0:
			e += 1
		k += 1
	i += 1
print(e)


n = int(input())
a = input()
b = []
b.append([0, 0])
x = y = ans = 0
for i in range(n):
	if a[i] == 'U':
		y += 1
		b.append([x, y])
	elif a[i] == 'D':
		y -= 1
		b.append([x, y])
	elif a[i] == 'L':
		x -= 1
		b.append([x, y])
	elif a[i] == 'R':
		x += 1
		b.append([x, y])
for i in range(n - 1):
	for j in range(i + 2, n + 1):
		if b[i] == b[j]:
			ans += 1
print(ans)


n = int(input())
s = str(input())
subs = res = [s[i:j] for i in range(len(s)) for j in range(i + 1, len(s) + 1)]
total = 0
for i in subs:
	if len(i) % 2 == 0:
		count_d = 0
		count_u = 0
		count_l = 0
		count_r = 0
		for letra in i:
			if letra == 'D':
				count_d += 1
			elif letra == 'U':
				count_u += 1
			elif letra == 'R':
				count_r += 1
			elif letra == 'L':
				count_l += 1
		if count_d == count_u and count_l == count_r:
			total += 1
print(total)


n = int(input())
codes = input()
urdl = [(0, 0, 0, 0)]
for code in codes:
	u = urdl[-1][0]
	r = urdl[-1][1]
	d = urdl[-1][2]
	l = urdl[-1][3]
	if code == 'U':
		u += 1
	elif code == 'R':
		r += 1
	elif code == 'D':
		d += 1
	elif code == 'L':
		l += 1
	urdl.append((u, r, d, l))
res = 0
for start in range(len(urdl) - 1):
	for end in range(start + 1, len(urdl)):
		a = urdl[start]
		b = urdl[end]
		if b[2] - a[2] == b[0] - a[0] and b[3] - a[3] == b[1] - a[1]:
			res += 1
print(res)


def chRet(st):
	ud = 0
	lr = 0
	for k in st:
		if k == 'U':
			ud += 1
		elif k == 'D':
			ud -= 1
		elif k == 'R':
			lr += 1
		elif k == 'L':
			lr -= 1
	if len(st) > 0 and ud == 0 and (lr == 0):
		return 1
	else:
		return 0
n = int(input())
s = input()
c = 0
for i in range(0, n):
	for j in range(2, n + 1, 1):
		c += chRet(s[i:j])
print(c)


n = int(input())
cmds = list(input())
ans = 0
x = 0
y = 0
for i in range(n):
	for j in range(i, n):
		x = 0
		y = 0
		for k in range(i, j + 1):
			if cmds[k] == 'U':
				y += 1
			elif cmds[k] == 'D':
				y -= 1
			elif cmds[k] == 'L':
				x -= 1
			else:
				x += 1
		if x == 0 and y == 0:
			ans += 1
print(ans)


n = int(input())
ans = 0
s = input()
for i in range(n):
	pl = [0, 0]
	st = [0, 0]
	if s[i] == 'U':
		pl[0] += 1
	if s[i] == 'D':
		pl[0] -= 1
	if s[i] == 'R':
		pl[1] += 1
	if s[i] == 'L':
		pl[1] -= 1
	for j in range(i + 1, n):
		if s[j] == 'U':
			pl[0] += 1
		if s[j] == 'D':
			pl[0] -= 1
		if s[j] == 'R':
			pl[1] += 1
		if s[j] == 'L':
			pl[1] -= 1
		if st == pl:
			ans += 1
print(ans)


n = int(input())
s = str(input())
subs = res = [s[i:j] for i in range(len(s)) for j in range(i + 1, len(s) + 1)]
total = 0
for i in subs:
	if len(i) % 2 == 0:
		countD = 0
		countU = 0
		countR = 0
		countL = 0
		for letra in i:
			if letra == 'D':
				countD += 1
			elif letra == 'U':
				countU += 1
			elif letra == 'R':
				countR += 1
			elif letra == 'L':
				countL += 1
		if countD == countU and countL == countR:
			total += 1
print(total)


I = input
R = range
C = str.count
n = int(I())
s = I()
a = [(0, 0, 0, 0)]
for i in R(1, n + 1):
	t = s[:i]
	a += [(C(t, 'L'), C(t, 'R'), C(t, 'U'), C(t, 'D'))]
print(sum((a[j][0] + a[i][1] == a[i][0] + a[j][1] and a[j][2] + a[i][3] == a[j][3] + a[i][2] for i in R(n) for j in R(i + 1, n + 1))))


n = int(input())
s = str(input())
(x, y, ans) = (0, 0, 0)
for i in range(n):
	for j in range(i, n):
		(x, y) = (0, 0)
		for k in range(i, j + 1):
			if s[k] == 'R':
				x += 1
			if s[k] == 'L':
				x -= 1
			if s[k] == 'U':
				y -= 1
			if s[k] == 'D':
				y += 1
		if x == 0 and y == 0:
			ans += 1
print(ans)


DIR = {'U': (-1, 0), 'R': (0, 1), 'D': (1, 0), 'L': (0, -1)}
try:
	while True:
		n = int(input())
		s = input()
		result = 0
		for i in range(len(s)):
			y = x = 0
			for c in s[i:]:
				t = DIR[c]
				y += t[0]
				x += t[1]
				if y == x == 0:
					result += 1
		print(result)
except EOFError:
	pass


def f(t):
	return t.count('U') == t.count('D') and t.count('L') == t.count('R')
(n, s) = (int(input()), input())
print(sum((f(s[i:j]) for i in range(n) for j in range(i + 1, n + 1))))


k = 0
a = int(input())
b = input()
u = [0] * 205
r = [0] * 205
l = [0] * 205
d = [0] * 205
for i in range(a):
	u[i + 1] = u[i]
	r[i + 1] = r[i]
	d[i + 1] = d[i]
	l[i + 1] = l[i]
	if b[i] == 'U':
		u[i + 1] += 1
	elif b[i] == 'R':
		r[i + 1] += 1
	elif b[i] == 'L':
		l[i + 1] += 1
	else:
		d[i + 1] += 1
for i in range(1, a + 1):
	for j in range(i, a + 1):
		if u[j] - u[i - 1] == d[j] - d[i - 1] and l[j] - l[i - 1] == r[j] - r[i - 1]:
			k += 1
print(k)


n = int(input())
string = input()
cnt = 0
for i in range(len(string)):
	for j in range(i + 1, len(string) + 1):
		x = 0
		y = 0
		for c in string[i:j]:
			if c == 'U':
				y += 1
			elif c == 'D':
				y -= 1
			elif c == 'L':
				x -= 1
			else:
				x += 1
		if x == y == 0:
			cnt += 1
print(cnt)


d = {'L': 1, 'R': -1, 'U': 1, 'D': -1}
n = int(input())
s = input()
i = 0
j = 2
cnt = 0
while True:
	while True:
		LR = 0
		UD = 0
		for k in s[i:i + j]:
			if k in 'LR':
				LR += d[k]
			else:
				UD += d[k]
		if LR == 0 and UD == 0:
			cnt += 1
		j += 2
		if i + j > n:
			i += 1
			j = 2
			break
	if i + j > n:
		break
print(cnt)


n = int(input())
s = input()
ans = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		k = s[i:j + 1]
		u = 0
		d = 0
		for a in k:
			if a == 'U':
				u += 1
			elif a == 'D':
				u -= 1
			elif a == 'R':
				d += 1
			elif a == 'L':
				d -= 1
		if u == 0 and d == 0:
			ans += 1
print(ans)


import sys
n = int(sys.stdin.readline())
commands = list(sys.stdin.readline().strip())
i = 0
j = 0
count = 0
for (i, elem) in enumerate(commands):
	u = 0
	d = 0
	l = 0
	r = 0
	for (j, elem2) in enumerate(commands[i:]):
		if elem2 == 'U':
			u += 1
		elif elem2 == 'D':
			d -= 1
		elif elem2 == 'L':
			l -= 1
		elif elem2 == 'R':
			r += 1
		j += 1
		if u + d == 0 and l + r == 0:
			count += 1
print(count)


dct = {'U': 1, 'D': -1, 'R': 200, 'L': -200}
com = int(input())
com1 = input()
count = 0
for i in range(com):
	for a in range(com + 1):
		if len(com1[i:a]) > 1:
			if sum([dct[x] for x in com1[i:a]]) == 0:
				count += 1
print(count)


n = int(input())
s = input()
mno = []
ans = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		mno.append(s[i:j])
	mno.append(s[i:])
for i in mno:
	if i.count('U') == i.count('D') and i.count('R') == i.count('L'):
		ans += 1
print(ans)


n = int(input())
a = input()
ans = 0
for i in range(n + 1):
	for j in range(i):
		l = a[j:i].count('L')
		r = a[j:i].count('R')
		u = a[j:i].count('U')
		d = a[j:i].count('D')
		if l == r and u == d:
			ans += 1
print(ans)


n = int(input())
l = input()
ans = 0
for i in range(2, n + 1):
	for j in range(n - i + 1):
		st = l[j:j + i]
		if st.count('L') == st.count('R') and st.count('U') == st.count('D'):
			ans += 1
print(ans)


def main():
	n = int(input()) + 1
	s = ' ' + input().strip()
	arr = [[0] * 2 for x in range(n)]
	(x, y) = (0, 0)
	ans = 0
	for i in range(len(s)):
		if s[i] == 'U':
			y += 1
		elif s[i] == 'D':
			y -= 1
		elif s[i] == 'L':
			x -= 1
		elif s[i] == 'R':
			x += 1
		arr[i] = [x, y]
		for j in range(i):
			if arr[j] == arr[i]:
				ans += 1
	print(ans)
main()


n = int(input())
str1 = input()
count = 0
for i in range(0, n):
	for j in range(i + 1, n + 1):
		substr = str1[i:j]
		if substr.count('U') == substr.count('D') and substr.count('L') == substr.count('R'):
			count += 1
print(count)


n = int(input())
s = input()
p = (0, 0)
d = {p: 1}
for i in s:
	if i == 'R':
		p = (p[0], p[1] + 1)
	if i == 'L':
		p = (p[0], p[1] - 1)
	if i == 'U':
		p = (p[0] + 1, p[1])
	if i == 'D':
		p = (p[0] - 1, p[1])
	d.update({p: d.get(p, 0) + 1})
sm = 0
for j in d:
	x = d.get(j)
	sm += (x - 1) * x // 2
print(sm)


n = int(input())
l = [*input()]
res = 0
m = [0, 0]
k = 0
z = 0
for i in range(n):
	(z, k) = (0, 0)
	for j in range(i, n):
		if l[j] == 'L':
			k += 1
		if l[j] == 'R':
			k -= 1
		if l[j] == 'U':
			z += 1
		if l[j] == 'D':
			z -= 1
		if k == 0:
			m[0] = 1
		else:
			m[0] = 0
		if z == 0:
			m[1] = 1
		else:
			m[1] = 0
		if m == [1, 1]:
			res += 1
print(res)


n = int(input())
c = input()
s = 0
for i in range(n):
	for j in range(i + 1, n):
		x = 0
		y = 0
		sub = c[i:j + 1]
		for k in sub:
			if k == 'L':
				x -= 1
			elif k == 'R':
				x += 1
			elif k == 'U':
				y += 1
			else:
				y -= 1
		if x == 0 and y == 0:
			s += 1
print(s)


n = int(input())
st = input()
curplace = [0, 0]
ans = 0
for i in range(n):
	for j in range(i, n):
		curplace = [0, 0]
		for k in range(i, j + 1):
			if st[k] == 'U':
				curplace[1] += 1
			elif st[k] == 'R':
				curplace[0] += 1
			elif st[k] == 'D':
				curplace[1] -= 1
			else:
				curplace[0] -= 1
		if curplace == [0, 0]:
			ans += 1
print(ans)


n = int(input())
s = input()
Vertikal = 0
Horizontal = 0
count = 0
for i in range(0, n):
	for j in range(i, n):
		if s[j] == 'U':
			Vertikal += 1
		elif s[j] == 'L':
			Horizontal -= 1
		elif s[j] == 'D':
			Vertikal -= 1
		elif s[j] == 'R':
			Horizontal += 1
		if Vertikal == 0 and Horizontal == 0:
			count = count + 1
	Vertikal = 0
	Horizontal = 0
print(count)


n = int(input())
ip = input()
total = 0
for x in range(len(ip)):
	temp = x
	while temp < n:
		position = 0
		for y in ip[x:temp + 1]:
			if y == 'R':
				position += 1
			elif y == 'L':
				position -= 1
			elif y == 'U':
				position += 200
			elif y == 'D':
				position -= 200
		if position == 0:
			total += 1
		temp += 1
print(total)


import sys
import math
import itertools
import functools
import collections
import operator

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def wr(arr):
	return ' '.join(map(str, arr))

def revn(n):
	return str(n)[::-1]

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base):
	newnumber = 0
	while number > 0:
		newnumber += number % base
		number //= base
	return newnumber

def cdiv(n, k):
	return n // k + (n % k != 0)
n = ii()
s = input()
ans = 0
for i in range(n):
	for j in range(i + 1, n + 1, 1):
		if s[i:j].count('U') == s[i:j].count('D') and s[i:j].count('R') == s[i:j].count('L'):
			ans += 1
print(ans)


n = int(input())
s = input()
d = {'U': (1, 0), 'R': (0, 1), 'D': (-1, 0), 'L': (0, -1)}

def f(t):
	(x, y) = (0, 0)
	for i in t:
		x += d[i][0]
		y += d[i][1]
	return (x, y) == (0, 0)
cnt = sum((f(s[L:R + 1]) for L in range(n) for R in range(L, n)))
print(cnt)


import math
n = int(input())
task = input()
l = [[0, 0]]
drp = {}
drp[0, 0] = 1
c = 0
for i in task:
	if i == 'U':
		l.append([l[-1][0], l[-1][1] + 1])
		if tuple(l[-1]) not in drp:
			drp[tuple(l[-1])] = 1
		else:
			drp[tuple(l[-1])] += 1
	if i == 'D':
		l.append([l[-1][0], l[-1][1] - 1])
		if tuple(l[-1]) not in drp:
			drp[tuple(l[-1])] = 1
		else:
			drp[tuple(l[-1])] += 1
	if i == 'L':
		l.append([l[-1][0] - 1, l[-1][1]])
		if tuple(l[-1]) not in drp:
			drp[tuple(l[-1])] = 1
		else:
			drp[tuple(l[-1])] += 1
	if i == 'R':
		l.append([l[-1][0] + 1, l[-1][1]])
		if tuple(l[-1]) not in drp:
			drp[tuple(l[-1])] = 1
		else:
			drp[tuple(l[-1])] += 1
for (k, v) in drp.items():
	if v >= 2:
		c += math.factorial(v) // 2 // math.factorial(v - 2)
print(c)


def main():
	n = int(input())
	chars = input()
	res = 0
	for i in range(n - 1):
		initial = [0, 0]
		for c in chars[i:]:
			if c == 'U':
				initial[0] += 1
			elif c == 'D':
				initial[0] -= 1
			elif c == 'R':
				initial[1] += 1
			else:
				initial[1] -= 1
			if initial[0] == 0 and initial[1] == 0:
				res += 1
	print(res)
main()


n = int(input())
s = input()
res = 0
for l in range(1, n + 1):
	for beg in range(0, n - l + 1):
		hor = 0
		ver = 0
		for i in range(beg, beg + l):
			if s[i] == 'U':
				ver += 1
			if s[i] == 'D':
				ver -= 1
			if s[i] == 'R':
				hor += 1
			if s[i] == 'L':
				hor -= 1
		if hor == 0 and ver == 0:
			res += 1
print(res)


n = int(input())
ch = str(input())
r = 0
a = 0
b = 0
T = [[0, 0]]
for k in range(n):
	if ch[k] == 'U':
		a += 1
	elif ch[k] == 'D':
		a -= 1
	elif ch[k] == 'R':
		b += 1
	else:
		b -= 1
	T += [[a, b]]
for i in range(1, n + 1):
	for j in range(i):
		if T[j] == T[i]:
			r += 1
print(r)


import sys
sys.stdin.readline()
line = sys.stdin.readline().strip()
count = 0
for (i, elem) in enumerate(line):
	(up, down, left, right) = (0, 0, 0, 0)
	for sub in line[i:]:
		if sub == 'U':
			up += 1
		if sub == 'D':
			down -= 1
		if sub == 'R':
			right += 1
		if sub == 'L':
			left -= 1
		if up + down == 0 and left + right == 0:
			count += 1
print(count)


class field:
	x = 0
	y = 0

	def go_up(self):
		self.y += 1

	def go_down(self):
		self.y -= 1

	def go_right(self):
		self.x += 1

	def go_left(self):
		self.x -= 1

	def equalStart(self):
		if self.x == 0 and self.y == 0:
			return True
		return False

def lineTest(line):
	myField = field()
	for i in range(len(line)):
		if line[i] == 'R':
			myField.go_right()
		if line[i] == 'L':
			myField.go_left()
		if line[i] == 'U':
			myField.go_up()
		if line[i] == 'D':
			myField.go_down()
	return myField.equalStart()
n = input()
n = int(n)
commands = input()
counter = 0
for i in range(len(commands)):
	subcom = commands[i:]
	for j in range(1, len(subcom) + 1):
		if lineTest(subcom[:j]):
			counter += 1
print(counter)


x = y = r = 0
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
d = 'LURD'
v = {(0, 0): 1}
for c in [*open(0)][1][:-1]:
	c = d.index(c)
	x += dx[c]
	y += dy[c]
	if (x, y) in v:
		r += v[x, y]
		v[x, y] += 1
	else:
		v[x, y] = 1
print(r)


import collections

def pair_add(a, b):
	return (a[0] + b[0], a[1] + b[1])
N = int(input())
seq = input()
trans = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
diff = [(0, 0)]
for d in seq:
	diff.append(pair_add(diff[-1], trans[d]))
cnt = collections.Counter(diff)
res = 0
for (k, v) in cnt.items():
	res += v * (v - 1)
print(res // 2)


n = int(input())
(ver, hor) = ([0], [0])
for ch in input():
	ver.append(ver[-1])
	hor.append(hor[-1])
	if ch == 'U':
		ver[-1] += 1
	if ch == 'D':
		ver[-1] -= 1
	if ch == 'L':
		hor[-1] += 1
	if ch == 'R':
		hor[-1] -= 1
ans = 0
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if hor[j] - hor[i - 1] == 0 and ver[j] - ver[i - 1] == 0:
			ans += 1
print(ans)


import sys
num = int(sys.stdin.readline().strip())
moves = str(sys.stdin.readline().strip()).lower()
ans = 0
for i in range(num):
	for j in range(i + 1, num + 1):
		(l, r, u, d) = (0, 0, 0, 0)
		for k in range(i, j):
			if moves[k] == 'l':
				l += 1
			elif moves[k] == 'r':
				r += 1
			elif moves[k] == 'u':
				u += 1
			else:
				d += 1
		if l == r and u == d:
			ans += 1
print(ans)


n = int(input())
s = input()
ans = 0
for i in range(n):
	for t in range(i + 1):
		s1 = s[t:i + 1]
		x = 0
		y = 0
		for e in range(len(s1)):
			if s1[e] == 'U':
				y += 1
			elif s1[e] == 'R':
				x += 1
			elif s1[e] == 'D':
				y -= 1
			else:
				x -= 1
		if x == y == 0:
			ans += 1
print(ans)


def main():
	from collections import defaultdict
	d = defaultdict(int)
	d[0, 0] += 1
	n = int(input())
	s = input()
	x = y = 0
	res = 0
	for i in s:
		if i == 'U':
			x += 1
		elif i == 'D':
			x -= 1
		elif i == 'L':
			y += 1
		else:
			y -= 1
		res += d[x, y]
		d[x, y] += 1
	print(res)
main()


def main():
	n = int(input())
	command = input()
	count = 0
	for i in range(n - 1):
		counts = {'U': 0, 'D': 0, 'L': 0, 'R': 0}
		for j in range(i, n):
			counts[command[j]] += 1
			if counts['U'] == counts['D'] and counts['L'] == counts['R']:
				count += 1
	print(count)
main()


def revient(a):
	U = 0
	D = 0
	L = 0
	R = 0
	for x in a:
		if x == 'U':
			U += 1
		elif x == 'D':
			D += 1
		elif x == 'L':
			L += 1
		else:
			R += 1
	if U == D and L == R:
		return 1
	else:
		return 0
a = int(input())
b = input()
c = []
compteur = 0
for x in b:
	c.append(x)
b = c
for x in range(0, a):
	liste = [b[x]]
	for y in range(1, a - x):
		liste.append(b[x + y])
		if revient(liste) == 1:
			compteur += 1
print(compteur)


a = int(input())
t = list(input())
u = 0
for k in range(a - 1):
	(x, y) = (0, 0)
	for j in range(k, a):
		if t[j] == 'U':
			y += 1
		elif t[j] == 'D':
			y -= 1
		elif t[j] == 'R':
			x += 1
		else:
			x -= 1
		if x == 0 and y == 0:
			u += 1
		else:
			pass
print(u)


import collections
import math
n = int(input())
s = input()
ans = 0
for i in range(len(s)):
	for j in range(i, len(s)):
		t = s[i:j + 1]
		if t.count('U') == t.count('D') and t.count('L') == t.count('R'):
			ans += 1
print(ans)


import io
import sys
import time
import random
start = time.clock()
n = int(input())
commands = list(input())
count = 0

def done(steps_dir):
	for v in steps_dir.values():
		if v % 4 != 0:
			return False
	return True
dirs = {'U': +1, 'D': -1, 'L': +1, 'R': -1}
coords = {'U': 0, 'D': 0, 'L': 1, 'R': 1}
for i in range(n):
	pos = [0, 0]
	for j in range(i, n):
		c = commands[j]
		pos[coords[c]] += dirs[c]
		if pos[0] == pos[1] == 0:
			count += 1
print(count)
dur = time.clock() - start


n = int(input())
A = list(input())
F = dict()
F['U'] = (0, 1)
F['D'] = (0, -1)
F['R'] = (1, 0)
F['L'] = (-1, 0)
for i in range(len(A)):
	A[i] = F[A[i]]
s = 0
for i in range(len(A)):
	for j in range(i + 1, len(A)):
		now = [0, 0]
		for k in range(i, j + 1):
			now[0] += A[k][0]
			now[1] += A[k][1]
		if now == [0, 0]:
			s += 1
print(s)


from collections import Counter
from sys import stdin

def solve(s: str):
	n = len(s)
	l = list(s)
	if n == 1:
		return 0
	res = 0
	for i in range(2, n + 1):
		for j in range(n - i + 1):
			i_ = l[j:j + i]
			c = Counter(i_)
			if c['U'] == c['D'] and c['R'] == c['L']:
				res += 1
	return res
_in = iter(stdin.readlines())
n = int(next(_in))
s = str(next(_in))[:-1]
print(solve(s))


Input = lambda : map(int, input().split())
n = int(input())
s = input()
ans = 0
for i in range(n):
	for j in range(n, i, -1):
		if s[i:j].count('R') == s[i:j].count('L') and s[i:j].count('U') == s[i:j].count('D'):
			ans += 1
print(ans)


n = int(input())
code = input()
c = 0
for i in range(n - 1):
	u = d = r = l = 0
	if code[i] == 'U':
		u += 1
	elif code[i] == 'D':
		d += 1
	elif code[i] == 'R':
		r += 1
	else:
		l += 1
	for j in range(i + 1, n):
		if code[j] == 'U':
			u += 1
		elif code[j] == 'D':
			d += 1
		elif code[j] == 'R':
			r += 1
		else:
			l += 1
		if u == d and r == l:
			c += 1
print(c)


n = int(input())
st = input()
b = 0
for i in range(n):
	for j in range(i + 1, n + 1):
		if len(st[i:j]) % 2 == 0:
			l = 0
			u = 0
			r = 0
			d = 0
			for k in st[i:j]:
				if k == 'L':
					l = l + 1
				elif k == 'U':
					u = u + 1
				elif k == 'D':
					d = d + 1
				elif k == 'R':
					r = r + 1
			if l == r and d == u:
				b = b + 1
print(b)


n = int(input())
k = 0
k1 = 0
d = {'0,0': 1}
s = input()
for x in s:
	if x == 'U':
		k += 1
	if x == 'D':
		k -= 1
	if x == 'R':
		k1 += 1
	if x == 'L':
		k1 -= 1
	w = str(k) + ',' + str(k1)
	d[w] = d.get(w, 0) + 1
cou = 0
for x in d:
	for i in range(1, d[x]):
		cou += i
print(cou)


(n, s) = (int(input()), input())
print(sum((i.count('L') == i.count('R') and i.count('D') == i.count('U') for i in [s[x:y + 1] for x in range(n) for y in range(x, n)])))


n = int(input())
string = input()
c = []
for char in string:
	if char == 'U':
		c.append(1)
	if char == 'D':
		c.append(-1)
	if char == 'R':
		c.append(2000)
	if char == 'L':
		c.append(-2000)
ans = 0
for k in range(2, len(c) + 1, 2):
	for i in range(0, len(c) - k + 1):
		t = sum(c[i:i + k])
		if t == 0:
			ans += 1
print(ans)


n = int(input())
s = input().rstrip()
count = 0
for i in range(len(s)):
	for j in range(i, len(s)):
		(x, y) = (0, 0)
		for c in s[i:j + 1]:
			if c == 'U':
				y += 1
			elif c == 'D':
				y -= 1
			elif c == 'L':
				x += 1
			elif c == 'R':
				x -= 1
		if x == 0 and y == 0:
			count += 1
print(count)


n = int(input(''))
s = str(input(''))
c = 0
for i in range(0, n - 1):
	for f in range(i + 2, n + 1):
		if s[i:f].count('R') == s[i:f].count('L') and s[i:f].count('U') == s[i:f].count('D'):
			c = c + 1
			r = 'S'
		else:
			r = ''
print(c)


from collections import Counter
n = int(input())
s = input()
k = 0
for i in range(n - 1):
	for j in range(i + 2, n + 1, 2):
		c = Counter(s[i:j])
		k += c['U'] == c['D'] and c['R'] == c['L']
print(k)


n = int(input())
ins = str(input())
pos = [(0, 0)] * n
for i in range(n):
	if ins[i] == 'U':
		if i == 0:
			pos[i] = (0, 1)
		else:
			pos[i] = (pos[i - 1][0], pos[i - 1][1] + 1)
	elif ins[i] == 'L':
		if i == 0:
			pos[i] = (-1, 0)
		else:
			pos[i] = (pos[i - 1][0] - 1, pos[i - 1][1])
	elif ins[i] == 'R':
		if i == 0:
			pos[i] = (1, 0)
		else:
			pos[i] = (pos[i - 1][0] + 1, pos[i - 1][1])
	elif ins[i] == 'D':
		if i == 0:
			pos[i] = (0, -1)
		else:
			pos[i] = (pos[i - 1][0], pos[i - 1][1] - 1)
ans = 0
d = dict()
d[0, 0] = 1
for i in pos:
	if i in d:
		ans += d[i]
		d[i] += 1
	else:
		d[i] = 1
print(str(ans))


n = int(input())
string = input()
counter = 0
for i in range(1, n + 1):
	for j in range(n - i + 1):
		if string[j:j + i].count('U') == string[j:j + i].count('D') and string[j:j + i].count('L') == string[j:j + i].count('R'):
			counter += 1
print(counter)


(a, b, count) = (int(input()), input(), 0)
for i in range(a - 1):
	for j in range(i + 1, a):
		c = b[i:j + 1]
		if c.count('D') == c.count('U') and c.count('L') == c.count('R'):
			count += 1
print(count)


numChars = int(input())
code = list(input())
x = 0
y = 0

def checkDifference(x, y, aList):
	moveX = 0
	moveY = 0
	for i in range(len(aList)):
		if aList[i] == 'U':
			moveY += 1
		elif aList[i] == 'D':
			moveY -= 1
		elif aList[i] == 'R':
			moveX += 1
		elif aList[i] == 'L':
			moveX -= 1
	if moveX == 0 and moveY == 0:
		return True
	else:
		return False
for i in range(len(code)):
	if code[i] == 'U':
		y += 1
	elif code[i] == 'D':
		y -= 1
	elif code[i] == 'R':
		x += 1
	elif code[i] == 'L':
		x -= 1
total = 0
for i in range(numChars):
	for h in range(i, numChars):
		newList = code[i:h + 1]
		if checkDifference(x, y, newList) and len(newList) != 0:
			total += 1
print(total)


n = int(input())
s = input()
ans = 0
for i in range(n):
	x = 0
	y = 0
	for j in range(i, n):
		if s[j] == 'L':
			x += 1
		elif s[j] == 'R':
			x -= 1
		elif s[j] == 'U':
			y += 1
		else:
			y -= 1
		if x == 0 and y == 0:
			ans += 1
print(ans)


def update_cords(ch, cords):
	if ch == 'L':
		cords[0] -= 1
	elif ch == 'R':
		cords[0] += 1
	elif ch == 'U':
		cords[1] = cords[1] + 1
	else:
		cords[1] -= 1
	return cords
n = int(input())
s = input()
count = 0
for i in range(n):
	cords = [0, 0]
	cords = update_cords(s[i], cords)
	for j in range(i + 1, n):
		cords = update_cords(s[j], cords)
		if cords[0] == 0 and cords[1] == 0:
			count += 1
print(count)


n = int(input())
data = input()
answer = 0
for i in range(n):
	for j in range(n):
		if i <= j:
			help = data[i:j + 1]
			L = help.count('L')
			R = help.count('R')
			U = help.count('U')
			D = help.count('D')
			if L == R and U == D:
				answer += 1
print(answer)


le = int(input())
s = input()
l = [[0, 0]]
curr = [0, 0]
for i in range(le):
	c = s[i]
	if c == 'U':
		curr[1] += 1
	elif c == 'R':
		curr[0] += 1
	elif c == 'L':
		curr[0] -= 1
	else:
		curr[1] -= 1
	l.append(curr[:])
l2 = []
for i in range(len(l)):
	if not l[i] in l2:
		l2.append(l[i][:])
l3 = [0] * len(l2)
for i in range(len(l2)):
	for j in range(len(l) - 1, -1, -1):
		if l2[i] == l[j]:
			l3[i] += 1
			l.pop(j)
out = 0
for val in l3:
	out += val * (val - 1) // 2
print(out)


from sys import stdin, stdout

def readline():
	return stdin.readline().rstrip()

def writeline(s):
	stdout.write(str(s) + '\n')
from collections import Counter
n = int(readline())
s = readline()
r = 0
for i in range(n):
	for j in range(i + 1, n + 1):
		c = Counter(s[i:j])
		if c['L'] == c['R'] and c['D'] == c['U']:
			r += 1
writeline(r)


def check(string):
	start = [0, 0]
	copy = start.copy()
	for i in range(len(string)):
		if string[i] == 'U':
			copy[0] += 1
		elif string[i] == 'D':
			copy[0] -= 1
		elif string[i] == 'R':
			copy[1] += 1
		elif string[i] == 'L':
			copy[1] -= 1
	if copy == start:
		return True
	return False

def robot():
	length = int(input())
	string = input()
	output = 0
	for i in range(len(string)):
		j = 2
		while j != len(string) + 1:
			if check(string[:j]):
				output += 1
			j += 1
		string = string[1:]
	return output
A = robot()
print(A)


n = int(input())
a = input()
c = 0
for s in range(n):
	for t in range(2, n - s + 1, 2):
		x = a[s:s + t]
		if x.count('U') == x.count('D') and x.count('R') == x.count('L'):
			c += 1
print(c)


n = int(input())
s = input()
count = 0
step = 2
while step <= n:
	for i in range(0, n - step + 1):
		temp = s[i:i + step]
		l = temp.count('L')
		r = temp.count('R')
		u = temp.count('U')
		d = temp.count('D')
		if l == r and u == d:
			count += 1
	step += 2
print(count)


n = int(input())
s = input()
x = 0
y = 0
ans = 0
for j in range(n):
	for k in range(n):
		ss = s[j:k + 1]
		for l in range(len(ss)):
			if ss[l] == 'U':
				y += 1
			elif ss[l] == 'D':
				y -= 1
			elif ss[l] == 'L':
				x -= 1
			elif ss[l] == 'R':
				x += 1
			else:
				pass
		if x == 0 and y == 0 and (len(ss) > 1):
			ans += 1
		else:
			pass
		x = 0
		y = 0
print(ans)


n1 = int(input())
lista = input()
cont = 0
for i in range(n1):
	x = 0
	y = 0
	for j in range(i, n1):
		s = lista[j]
		if s == 'L':
			x += 1
		elif s == 'R':
			x -= 1
		if s == 'U':
			y += 1
		elif s == 'D':
			y -= 1
		if x == 0 and y == 0:
			cont += 1
print(cont)


n = int(input())
task = input()
l = [[0, 0]]
drp = {}
drp[0, 0] = 1
c = 0
for i in task:
	if i == 'U':
		l.append([l[-1][0], l[-1][1] + 1])
		if tuple(l[-1]) not in drp:
			drp[tuple(l[-1])] = 1
		else:
			drp[tuple(l[-1])] += 1
	elif i == 'D':
		l.append([l[-1][0], l[-1][1] - 1])
		if tuple(l[-1]) not in drp:
			drp[tuple(l[-1])] = 1
		else:
			drp[tuple(l[-1])] += 1
	elif i == 'L':
		l.append([l[-1][0] - 1, l[-1][1]])
		if tuple(l[-1]) not in drp:
			drp[tuple(l[-1])] = 1
		else:
			drp[tuple(l[-1])] += 1
	else:
		l.append([l[-1][0] + 1, l[-1][1]])
		if tuple(l[-1]) not in drp:
			drp[tuple(l[-1])] = 1
		else:
			drp[tuple(l[-1])] += 1
for (k, v) in drp.items():
	if v >= 2:
		c += v * (v - 1) // 2
print(c)


n = int(input())
s = input()
ans = 0
for i in range(len(s)):
	for j in range(i + 1, len(s)):
		m = {'L': 0, 'R': 0, 'U': 0, 'D': 0}
		s1 = s[i:j + 1]
		for x in s1:
			m[x] += 1
		if m['L'] == m['R'] and m['U'] == m['D']:
			ans += 1
print(ans)


n = int(input())
s = input()
a = 0
for x in range(n):
	for y in range(x + 1, n + 1):
		t = s[x:y]
		p = q = 0
		for z in t:
			if z == 'R':
				p += 1
			elif z == 'L':
				p -= 1
			elif z == 'U':
				q += 1
			else:
				q -= 1
		if p == q == 0:
			a += 1
print(a)


n = int(input())
com = input()
x = [0] * n
y = [0] * n
ans = 0
for i in range(n):
	if com[i] == 'U':
		y[i] = 1
	elif com[i] == 'D':
		y[i] = -1
	elif com[i] == 'R':
		x[i] = 1
	else:
		x[i] = -1
for i in range(1, n):
	for j in range(n - i):
		if sum(x[j:j + i + 1]) == 0 and sum(y[j:j + i + 1]) == 0:
			ans += 1
print(ans)


def man(daf):
	res = [0, 0]
	for x in daf:
		if x == 'U':
			res[1] += 1
		elif x == 'D':
			res[1] -= 1
		elif x == 'L':
			res[0] -= 1
		else:
			res[0] += 1
	return res
n = int(input())
daf = list(input())
total = 0
for i in range(n):
	for j in range(i + 1, n + 1):
		daf2 = daf[i:j]
		if man(daf2) == [0, 0]:
			total += 1
print(total)


n = int(input())
d = input()
count = 0
i = 0

def setDi(di, hori, veri):
	if di in ['U', 'D']:
		if di == 'U':
			veri += 1
		else:
			veri -= 1
	elif di in ['L', 'R']:
		if di == 'R':
			hori += 1
		else:
			hori -= 1
	return (hori, veri)
while i <= len(d) - 2:
	(hori, veri) = (0, 0)
	if d[i] in ['U', 'D']:
		if d[i] == 'U':
			veri += 1
		else:
			veri -= 1
	elif d[i] in ['L', 'R']:
		if d[i] == 'R':
			hori += 1
		else:
			hori -= 1
	j = i + 1
	while j <= len(d) - 1:
		if d[j] == 'U':
			veri += 1
		elif d[j] == 'D':
			veri -= 1
		elif d[j] == 'L':
			hori -= 1
		elif d[j] == 'R':
			hori += 1
		if veri == 0 and hori == 0:
			count += 1
		j += 1
	i += 1
print(count)


R = 0
U = 0
count = 0
n = int(input())
t = input()
for i in range(n):
	R = 0
	U = 0
	for j in range(i, n):
		if t[j] == 'R':
			R = R + 1
		elif t[j] == 'L':
			R = R - 1
		elif t[j] == 'U':
			U = U + 1
		else:
			U = U - 1
		if R == 0 and U == 0:
			count = count + 1
print(count)


n = int(input())
s = input()

def udrl(z):
	l = [0, 0]
	for i in z:
		if i == 'U':
			l[1] += 1
		elif i == 'D':
			l[1] -= 1
		elif i == 'L':
			l[0] -= 1
		elif i == 'R':
			l[0] += 1
	return l
k = 0
for i in range(len(s)):
	for j in range(i, len(s)):
		if udrl(s[i:j + 1]) == [0, 0]:
			k += 1
print(k)


def main():
	input()
	d = {(0, 0): 1}
	x = y = 0
	for c in input():
		if c == 'R':
			x += 1
		elif c == 'L':
			x -= 1
		elif c == 'U':
			y += 1
		else:
			y -= 1
		d[x, y] = d.get((x, y), 0) + 1
	print(sum((v * (v - 1) for v in d.values())) // 2)
main()


n = int(input())
l = input()
v = []
h = []
for c in l:
	if c == 'U':
		v += [1]
	elif c == 'D':
		v += [-1]
	else:
		v += [0]
	if c == 'R':
		h += [1]
	elif c == 'L':
		h += [-1]
	else:
		h += [0]
for i in range(1, n):
	v[i] += v[i - 1]
	h[i] += h[i - 1]
v = [0] + v
h = [0] + h
a = 0
for i in range(n):
	for j in range(i, n):
		if h[j + 1] == h[i] and v[j + 1] == v[i]:
			a += 1
print(a)


n = int(input())
coordinate = [(0, 0) for i in range(n + 1)]
commands = input()
ans = 0
for i in range(1, n + 1):
	if commands[i - 1] == 'U':
		coordinate[i] = (coordinate[i - 1][0], coordinate[i - 1][1] + 1)
	elif commands[i - 1] == 'D':
		coordinate[i] = (coordinate[i - 1][0], coordinate[i - 1][1] - 1)
	elif commands[i - 1] == 'R':
		coordinate[i] = (coordinate[i - 1][0] + 1, coordinate[i - 1][1])
	else:
		coordinate[i] = (coordinate[i - 1][0] - 1, coordinate[i - 1][1])
for i in range(n):
	for j in range(i + 1, n + 1):
		if coordinate[i] == coordinate[j]:
			ans += 1
print(ans)


def move_robot(pos, move):
	if move == 'U':
		pos[1] += 1
	elif move == 'D':
		pos[1] -= 1
	elif move == 'L':
		pos[0] -= 1
	elif move == 'R':
		pos[0] += 1
	return pos
n = int(input())
str = input()
ans = 0
for i in range(len(str)):
	pos = [0, 0]
	for j in range(i, len(str)):
		pos = move_robot(pos, str[j])
		if pos == [0, 0]:
			ans += 1
print(ans)


n = int(input())
l = list(input())
ans = 0
for i in range(n):
	for j in range(i + 1, n + 1):
		(x, y) = (0, 0)
		for k in range(i, j):
			if l[k] == 'D':
				y -= 1
			if l[k] == 'U':
				y += 1
			if l[k] == 'L':
				x -= 1
			if l[k] == 'R':
				x += 1
		if x == y == 0:
			ans += 1
print(ans)


w = int(input())
q = input()
r = 0
for i in range(0, w - 1):
	for j in range(1, w - i, 2):
		a = q[i:i + j + 1]
		if (a.count('R') == a.count('L')) & (a.count('U') == a.count('D')):
			r += 1
print(r)


a = {'U': 1, 'D': -1, 'R': -200, 'L': 200}
j = int(input())
d = 0
b = input()
for x in range(j):
	for z in range(j + 1):
		c = 0
		for y in b[x:z]:
			c += a[y]
		if c == 0 and len(b[x:z]) != 0:
			d += 1
print(d)


n = int(input())
str = input()
ans = 0
for a in range(n + 1):
	for b in range(n + 1):
		if a < b:
			(x, y) = (0, 0)
			s = ''
			for c in str[a:b]:
				if c == 'U':
					y += 1
				if c == 'R':
					x -= 1
				if c == 'D':
					y -= 1
				if c == 'L':
					x += 1
			if x == 0 and y == 0:
				ans += 1
print(ans)


n = int(input())
s = input()
d = {'L': [0, -1], 'R': [0, 1], 'U': [-1, 0], 'D': [1, 0]}
a = [[0, 0]]
for i in s:
	a.append([a[-1][0] + d[i][0], a[-1][1] + d[i][1]])
x = 0
for i in range(n):
	for j in range(i + 2, n + 1):
		if a[j][0] - a[i][0] == a[j][1] - a[i][1] == 0:
			x += 1
print(x)


n = input()
grid = [[0 for _ in range(500)] for _ in range(500)]
(x, y) = (250, 250)
grid[x][y] = 1
for com in list(input()):
	if com == 'U':
		y -= 1
	elif com == 'D':
		y += 1
	elif com == 'R':
		x += 1
	else:
		x -= 1
	grid[x][y] += 1
print(sum(map(lambda x: x * (x - 1) // 2, [grid[x][y] for x in range(500) for y in range(500)])))


n = int(input())
s = input()
cnt = 0
ud = 0
lr = 0
for i in range(n):
	(ud, lr) = (0, 0)
	if s[i] == 'U':
		ud = 1
	elif s[i] == 'D':
		ud = -1
	elif s[i] == 'R':
		lr = 1
	elif s[i] == 'L':
		lr = -1
	for j in range(i + 1, n):
		if s[j] == 'U':
			ud += 1
		elif s[j] == 'D':
			ud -= 1
		elif s[j] == 'R':
			lr += 1
		elif s[j] == 'L':
			lr -= 1
		if lr == 0 and ud == 0:
			cnt += 1
print(cnt)


N = int(input())
S = input()
ans = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		segment = S[i:j + 1]
		if segment.count('R') == segment.count('L') and segment.count('D') == segment.count('U'):
			ans += 1
print(ans)


n = int(input())
moves = list(input())
mapping = {'U': 1, 'D': -1, 'R': 1, 'L': -1}
ans = 0
for i in range(n):
	hor = 0
	vert = 0
	for j in range(i, n):
		move = moves[j]
		if move == 'U' or move == 'D':
			vert += mapping[move]
		else:
			hor += mapping[move]
		if hor == 0 and vert == 0:
			ans += 1
print(ans)


n = int(input())
s = input()
t = []
for i in range(len(s)):
	for j in range(len(s), i, -1):
		t.append(s[i:j])
cnt = 0
for i in t:
	if i.count('U') == i.count('D') and i.count('R') == i.count('L'):
		cnt += 1
print(cnt)


def retorna(caminho):
	(l, r, u, d) = (0, 0, 0, 0)
	for e in caminho:
		if e == 'L':
			l += 1
		elif e == 'R':
			r += 1
		elif e == 'U':
			u += 1
		elif e == 'D':
			d += 1
	if l == r and u == d and (u + d + l + r != 0):
		return True
	return False
n = int(input())
moves = input()
if n == 1:
	print(0)
else:
	i = 0
	ans = 0
	while i < n - 1:
		for j in range(1, len(moves)):
			if retorna(moves[i:j + 1]):
				ans += 1
		i += 1
	print(ans)


a = [0, 0]

def ok(x, a):
	if x == 'L':
		a[0] -= 1
	elif x == 'R':
		a[0] += 1
	elif x == 'U':
		a[1] += 1
	elif x == 'D':
		a[1] -= 1
g = int(input())
s = input()
j = 0
for i in range(len(s)):
	a = [0, 0]
	for z in range(i, len(s)):
		ok(s[z], a)
		if a == [0, 0]:
			j += 1
print(j)


n = int(input())
l = input()
c = 0
for i in range(n - 1):
	for j in range(i + 2, n + 1):
		t = l[i:j]
		if t.count('L') == t.count('R') and t.count('U') == t.count('D'):
			c += 1
print(c)


n = int(input())
(s, c) = (input(), 0)
for i in range(n):
	for j in range(1, n - i, 2):
		z = s[i:i + j + 1]
		c += z.count('R') == z.count('L') and z.count('U') == z.count('D')
print(c)


course = {'U': (0, 1), 'D': (0, -1), 'L': (-1, 0), 'R': (1, 0)}

class Bot:

	def __init__(self):
		self.pos = (0, 0)
		self.dir = ''

	def goto(self, way):
		p = self.pos
		c = course[way]
		self.pos = (p[0] + c[0], p[1] + c[1])
bot = Bot()
poses = {(0, 0): 0}
cycles = 0
_ = input()
steps = input()
for step in steps:
	bot.dir = step
	poses[bot.pos] += 1
	bot.goto(step)
	if poses.get(bot.pos):
		cycles += poses[bot.pos]
	else:
		poses[bot.pos] = 0
print(cycles)


import sys
import collections
case = int(sys.stdin.readline())
oper = sys.stdin.readline()[:-1]
tot = 0
for left in range(len(oper)):
	index = [0, 0]
	for right in range(left, len(oper)):
		if oper[right] == 'L':
			index[0] -= 1
		elif oper[right] == 'R':
			index[0] += 1
		elif oper[right] == 'U':
			index[1] += 1
		elif oper[right] == 'D':
			index[1] -= 1
		if index == [0, 0]:
			tot += 1
print(tot)


ea = int(input())
jalur = input()
ancol = 0
for i in range(ea - 1):
	u = 0
	d = 0
	l = 0
	r = 0
	for k in jalur[i:]:
		if k == 'U':
			u += 1
		elif k == 'D':
			d += 1
		elif k == 'L':
			l += 1
		else:
			r += 1
		if u - d == 0 and l - r == 0:
			ancol += 1
print(ancol)


n = int(input())
s = input()
ret = 0
for i in range(n):
	for j in range(i + 1, n + 1):
		count = {}
		for k in range(i, j):
			count[s[k]] = count.get(s[k], 0) + 1
		eq = len(count) > 1
		if 'U' in count or 'D' in count:
			if 'D' not in count or 'U' not in count:
				eq = False
			else:
				eq &= count['U'] == count['D']
		if 'L' in count or 'R' in count:
			if 'R' not in count or 'L' not in count:
				eq = False
			else:
				eq &= count['L'] == count['R']
		ret += eq
print(ret)


n = int(input())
commands = input()
vertical = [0]
horizontal = [0]
for i in range(1, n + 1):
	vert_diff = 0
	hor_diff = 0
	if commands[i - 1] == 'U':
		vert_diff = 1
	elif commands[i - 1] == 'D':
		vert_diff = -1
	elif commands[i - 1] == 'R':
		hor_diff = 1
	else:
		hor_diff = -1
	vertical.append(vertical[i - 1] + vert_diff)
	horizontal.append(horizontal[i - 1] + hor_diff)
total = 0
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		hor_diff = horizontal[j] - horizontal[i - 1]
		vert_diff = vertical[j] - vertical[i - 1]
		if hor_diff == 0 and vert_diff == 0:
			total += 1
print(total)


n = int(input())
s = list(input())
i = 0
counter = 0
while i < n:
	ans = []
	for j in range(i, n):
		ans.append(s[j])
		if ans.count('L') == ans.count('R') and ans.count('D') == ans.count('U'):
			counter += 1
	i += 1
print(counter)


from sys import stdin
max_val = int(10000000000000.0)
min_val = int(-10000000000000.0)

def read_int():
	return int(stdin.readline())

def read_ints():
	return [int(x) for x in stdin.readline().split()]

def read_str():
	return input()

def read_strs():
	return [x for x in stdin.readline().split()]
lens = read_int()
done = input()
ways = 0
for i in range(lens):
	for j in range(i + 1, lens + 1):
		curr = done[i:j]
		ways += curr.count('L') == curr.count('R') and curr.count('U') == curr.count('D')
print(ways)


n = int(input())
a = []
a = input()
count = 0
i = 0
j = 0
while i < len(a):
	j = i
	while j < len(a):
		countL = a[i:j + 1].count('L')
		countU = a[i:j + 1].count('U')
		countR = a[i:j + 1].count('R')
		countD = a[i:j + 1].count('D')
		if countL == countR and countU == countD:
			count = count + 1
		j = j + 1
	i = i + 1
print(count)


import sys
n = int(sys.stdin.readline())
moves = sys.stdin.readline()
up = []
left = []
right = []
down = []
for i in range(n + 1):
	up.append(0)
	right.append(0)
	down.append(0)
	left.append(0)
for i in range(n):
	if moves[i] == 'U':
		up[i + 1] += 1
	elif moves[i] == 'D':
		down[i + 1] += 1
	elif moves[i] == 'L':
		left[i + 1] += 1
	elif moves[i] == 'R':
		right[i + 1] += 1
for i in range(1, n + 1):
	up[i] += up[i - 1]
	down[i] += down[i - 1]
	right[i] += right[i - 1]
	left[i] += left[i - 1]
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		horizontal = up[j + 1] - up[i] - (down[j + 1] - down[i])
		vertical = right[j + 1] - right[i] - (left[j + 1] - left[i])
		if horizontal == 0 and vertical == 0:
			ans += 1
print(ans)


n = int(input())
s = input().strip()
ans = 0
for i in range(n):
	for j in range(i + 1, n + 1):
		temp = s[i:j]
		if temp.count('U') == temp.count('D') and temp.count('R') == temp.count('L'):
			ans += 1
print(ans)


UP = 'U'
DOWN = 'D'
LEFT = 'L'
RIGHT = 'R'

def solve():
	length = int(input().strip())
	seq = input().strip()
	updown = 0
	leftright = 0
	moves = [(updown, leftright)]
	for cmd in seq:
		if cmd == UP:
			updown += 1
		elif cmd == DOWN:
			updown -= 1
		elif cmd == RIGHT:
			leftright += 1
		else:
			leftright -= 1
		moves.append((updown, leftright))
	state_length = len(moves)
	count = 0
	for i in range(state_length):
		(ud1, lr1) = moves[i]
		for j in range(i + 1, state_length):
			(ud2, lr2) = moves[j]
			if ud2 - ud1 == 0 and lr2 - lr1 == 0:
				count += 1
	print(count)
solve()


n = int(input())
s = input()
su = 0
for i in range(0, n - 1):
	for i1 in range(i + 1, n):
		x = 0
		y = 0
		for c in s[i:i1 + 1]:
			if c == 'U':
				y += 1
			elif c == 'D':
				y -= 1
			elif c == 'R':
				x += 1
			elif c == 'L':
				x -= 1
		if x == 0 and y == 0:
			su += 1
print(su)


size = int(input())
s = [int(x.replace('L', '-1').replace('R', '1').replace('U', '250').replace('D', '-250')) for x in input()]
total = 0
for i in range(2, size + 1):
	for j in range(0, size + 1 - i):
		if sum(s[j:j + i]) == 0:
			total = total + 1
print(total)


def noMove(cmd):
	if (cmd.count('U'), cmd.count('R')) == (cmd.count('D'), cmd.count('L')):
		return True
	else:
		return False

def css(cmd, n):
	count = 0
	for i in range(n):
		c = i + 1
		for j in range(n - i):
			t = cmd[j:j + c]
			if noMove(t) == True:
				count += 1
	return count
n = int(input())
cmd = list(input())
print(css(cmd, n))


n = int(input())
text = input()
counter = 0
for i in range(n):
	for j in range(i + 1, n, 1):
		dx = dy = 0
		command = text[i:j + 1]
		m = len(command)
		for k in range(m):
			if command[k] == 'U':
				dy += 1
			elif command[k] == 'R':
				dx += 1
			elif command[k] == 'D':
				dy -= 1
			elif command[k] == 'L':
				dx -= 1
		counter += 1 if dx == 0 and dy == 0 else 0
print(counter)


import sys

def is_closed(s):
	return s.count('L') == s.count('R') and s.count('D') == s.count('U')

def main():
	sys.stdin.readline()
	s = sys.stdin.readline()
	res = 0
	for i in range(len(s) - 1):
		for j in range(i + 1, len(s)):
			res += is_closed(s[i:j])
	print(res)
main()


input()
X = input()
Count = 0
for i in range(len(X)):
	(Vert, Horiz) = (0, 0)
	Vert += 1 if X[i] == 'U' else -1 if X[i] == 'D' else 0
	Horiz += 1 if X[i] == 'R' else -1 if X[i] == 'L' else 0
	for j in range(i + 1, len(X)):
		Vert += 1 if X[j] == 'U' else -1 if X[j] == 'D' else 0
		Horiz += 1 if X[j] == 'R' else -1 if X[j] == 'L' else 0
		if Vert == 0 and Horiz == 0:
			Count += 1
print(Count)


n = int(input())
s = input()
c = 0
for i in range(n):
	(x, y) = (0, 0)
	for j in range(i, n):
		if s[j] == 'U':
			y += 1
		elif s[j] == 'R':
			x += 1
		elif s[j] == 'D':
			y -= 1
		else:
			x -= 1
		if x == 0 and y == 0:
			c += 1
print(c)


n = int(input())
s = input()
ans = 0
for l in range(n - 1):
	for r in range(l + 1, n + 1):
		(y, x) = (0, 0)
		for c in s[l:r]:
			if c == 'U':
				y += 1
			elif c == 'D':
				y -= 1
			elif c == 'R':
				x += 1
			elif c == 'L':
				x -= 1
		if y == 0 and x == 0:
			ans += 1
print(ans)


n = int(input())
cur = input()
dp = [[[0, 0] for j in range(n + 1)] for i in range(n + 1)]
for i in range(0, n):
	for j in range(i, n):
		cur_xy = dp[i][j][:]
		if cur[j] == 'U':
			cur_xy[1] += 1
		elif cur[j] == 'D':
			cur_xy[1] -= 1
		elif cur[j] == 'R':
			cur_xy[0] += 1
		elif cur[j] == 'L':
			cur_xy[0] -= 1
		dp[i][j + 1] = cur_xy
ans = 0
for i in range(0, n + 1):
	for j in range(i + 1, n + 1):
		if dp[i][j] == [0, 0]:
			ans += 1
print(ans)


import time
n = int(input())
a = list(input())
start = time.time()
ans = 0
for i in range(n):
	ud = 0
	lr = 0
	for j in range(i, n):
		if a[j] == 'U':
			ud += 1
		if a[j] == 'D':
			ud -= 1
		if a[j] == 'R':
			lr += 1
		if a[j] == 'L':
			lr -= 1
		if lr == 0 and ud == 0:
			ans += 1
print(ans)
finish = time.time()


n = int(input())
s = input()
count = 0
for i in range(0, len(s)):
	(x, y) = (0, 0)
	for j in range(i, len(s)):
		if s[j] == 'U':
			y += 1
		elif s[j] == 'R':
			x += 1
		elif s[j] == 'D':
			y -= 1
		elif s[j] == 'L':
			x -= 1
		else:
			assert False
		if x == 0 and y == 0:
			count += 1
print(count)


n = int(input())
s = input()
result = 0
for start in range(n):
	for finish in range(start + 1, n + 1):
		tmp = s[start:finish]
		if tmp.count('U') == tmp.count('D') and tmp.count('L') == tmp.count('R'):
			result += 1
print(result)


N = int(input())
comm = input()
count = 0
for i in range(N - 1):
	for j in range(i + 1, N + 1):
		subcomm = comm[i:j]
		r = 0
		c = 0
		for ch in subcomm:
			if ch == 'U':
				r += 1
			if ch == 'D':
				r -= 1
			if ch == 'L':
				c -= 1
			if ch == 'R':
				c += 1
		if r == 0 and c == 0:
			count += 1
print(count)


leng = int(input())
source = input()
lst = {}
for i in range(leng):
	for j in range(i + 1, leng):
		a = source[i:j + 1]
		if a in lst:
			lst[a] += 1
		else:
			x = a.count('R') - a.count('L')
			y = a.count('U') - a.count('D')
			if x == y == 0:
				lst[a] = 1
print(sum(lst.values()))


import sys
import math
import bisect
import itertools
import random
import re

def is_satisfied(s):
	d = {'L': 0, 'U': 0, 'R': 0, 'D': 0}
	for c in s:
		d[c] += 1
	return d['L'] == d['R'] and d['U'] == d['D']

def solve(s):
	n = len(s)
	ans = 0
	for i in range(n):
		for j in range(i, n):
			if is_satisfied(s[i:j + 1]):
				ans += 1
	return ans

def main():
	n = int(input())
	ans = solve(input())
	print(ans)
main()


n = int(input())
s = input()
dx = 0
dy = 0
c = 0
for i in range(n):
	if s[i] == 'U':
		dy = 1
		dx = 0
	elif s[i] == 'D':
		dy = -1
		dx = 0
	elif s[i] == 'R':
		dx = 1
		dy = 0
	else:
		dx = -1
		dy = 0
	for j in range(i + 1, n):
		if s[j] == 'U':
			dy += 1
		elif s[j] == 'D':
			dy -= 1
		elif s[j] == 'R':
			dx += 1
		else:
			dx -= 1
		if dx == 0 and dy == 0:
			c += 1
print(c)