Consider a grid of size $n \times n$. The rows are numbered top to bottom from $1$ to $n$, the columns are numbered left to right from $1$ to $n$.

The robot is positioned in a cell $(1, 1)$. It can perform two types of moves:

D — move one cell down;

R — move one cell right.

The robot is not allowed to move outside the grid.

You are given a sequence of moves $s$ — the initial path of the robot. This path doesn't lead the robot outside the grid.

You are allowed to perform an arbitrary number of modifications to it (possibly, zero). With one modification, you can duplicate one move in the sequence. That is, replace a single occurrence of D with DD or a single occurrence of R with RR.

Count the number of cells such that there exists at least one sequence of modifications that the robot visits this cell on the modified path and doesn't move outside the grid.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains the single integer $n$ ($2 \le n \le 10^8$) — the number of rows and columns in the grid.

The second line of each testcase contains a non-empty string $s$, consisting only of characters D and R, — the initial path of the robot. This path doesn't lead the robot outside the grid.

The total length of strings $s$ over all testcases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each testcase, print a single integer — the number of cells such that there exists at least one sequence of modifications that the robot visits this cell on the modified path and doesn't move outside the grid.


-----Examples-----

Input
3
4
RD
5
DRDRDRDR
3
D
Output
13
9
3


-----Note-----

In the first testcase, it's enough to consider the following modified paths:

RD $\rightarrow$ RRD $\rightarrow$ RRRD $\rightarrow$ RRRDD $\rightarrow$ RRRDDD — this path visits cells $(1, 1)$, $(1, 2)$, $(1, 3)$, $(1, 4)$, $(2, 4)$, $(3, 4)$ and $(4, 4)$;

RD $\rightarrow$ RRD $\rightarrow$ RRDD $\rightarrow$ RRDDD — this path visits cells $(1, 1)$, $(1, 2)$, $(1, 3)$, $(2, 3)$, $(3, 3)$ and $(4, 3)$;

RD $\rightarrow$ RDD $\rightarrow$ RDDD — this path visits cells $(1, 1)$, $(1, 2)$, $(2, 2)$, $(3, 2)$ and $(4, 2)$.

Thus, the cells that are visited on at least one modified path are: $(1, 1)$, $(1, 2)$, $(1, 3)$, $(1, 4)$, $(2, 2)$, $(2, 3)$, $(2, 4)$, $(3, 2)$, $(3, 3)$, $(3, 4)$, $(4, 2)$, $(4, 3)$ and $(4, 4)$.

In the second testcase, there is no way to modify the sequence without moving the robot outside the grid. So the only visited cells are the ones that are visited on the path DRDRDRDR.

In the third testcase, the cells that are visited on at least one modified path are: $(1, 1)$, $(2, 1)$ and $(3, 1)$.

Here are the cells for all testcases:

Difficulty: HARD
Tags: Combinatorics

Implementation

Complete search

Mathematics

Data structures
Skill types: Data structures

Complete search

Starter code:

Solutions:
from enum import Enum, auto
import copy
import sys
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		init_path = input().strip()
		if 'R' not in init_path or 'D' not in init_path:
			print(n)
			continue
		r_num = init_path.count('R')
		d_num = init_path.count('D')
		res = r_num + d_num + 1
		if r_num < n:
			r_index = init_path.find('R')
			chuga = d_num + 1 - r_index
			res += (n - r_num - 1) * chuga
		if d_num < n:
			d_index = init_path.find('D')
			chuga = r_num + 1 - d_index
			res += (n - d_num - 1) * chuga
		res += (n - 1 - r_num) * (n - 1 - d_num)
		print(res)
main()


import sys

def input():
	return sys.stdin.readline()[:-1]

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

def solve():
	n = int(input())
	s = input()
	ans = len(s) + 1
	r_cnt = s.count('R')
	d_cnt = len(s) - r_cnt
	width = r_cnt + 1
	height = d_cnt + 1
	if r_cnt and d_cnt:
		ans += (n - width) * (n - height)
	d = s.find('D')
	if d != -1:
		ans += (width - d) * (n - height)
	r = s.find('R')
	if r != -1:
		ans += (height - r) * (n - width)
	print(ans)
t = int(input())
for __ in range(t):
	solve()


def calc(s, n):
	ld = s.find('R')
	res = ld * (n - 1)
	y = 0
	for i in range(len(s) - 1, ld - 1, -1):
		if s[i] == 'D':
			res += y
		else:
			y += 1
	return res
out = ''
for _ in range(int(input())):
	n = int(input())
	s = input()
	if s.count(s[0]) == len(s):
		out += str(n) + '\n'
		continue
	ans = n * n
	ans -= calc(s, n)
	ans -= calc(''.join(['D' if c == 'R' else 'R' for c in s]), n)
	out += str(ans) + '\n'
print(out)


Z = input
for _ in range(int(Z())):
	m = int(Z())
	s = Z()
	n = len(s)
	y = chr(150 - ord(s[0]))
	x = (s + y).index(y)
	print(1 + n + (m - x) * m - (1 + s.count('D', x)) * (1 + s.count('R', x)) if x < n else m)


import math

def solve():
	n = int(input())
	s = input()
	l = len(s)
	ar = s.count('R')
	al = l - ar
	ans = mk = cntl = cntr = 0
	if ar == 0 or al == 0:
		return n
	for i in s:
		if i == 'R':
			cntr += 1
			ans += al - cntl if cntl else n - 1
		else:
			cntl += 1
			ans += ar - cntr if cntr else n - 1
	return n * n - ans
t = input()
for tt in range(int(t)):
	print(solve())


def solve():
	t = int(input())
	for r in range(t):
		n = int(input())
		path = input()
		cnt_r = path.count('R')
		cnt_d = path.count('D')
		if cnt_r == 0 or cnt_d == 0:
			result = n
		else:
			move_r = n - cnt_r - 1
			move_d = n - cnt_d - 1
			result = 1
			cur_char = ''
			prev_char = ''
			last_char = ''
			for cur_char in path:
				result += 1
				if prev_char != cur_char:
					last_char = prev_char
				if last_char == 'R':
					result += move_r
				elif last_char == 'D':
					result += move_d
				prev_char = cur_char
			result += (1 + move_r) * (1 + move_d)
			result -= 1
		print(result)
solve()


def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		t = ''.join(['D' if i == 'R' else 'R' for i in s])
		poss = s.find('R')
		post = t.find('R')
		if s == 'R' * len(s) or s == 'D' * len(s):
			print(n)
			continue
		(res, cnta, cntb) = (poss * (n - 1) + post * (n - 1), 0, 0)
		for i in range(len(s) - 1, poss - 1, -1):
			if s[i] == 'D':
				res += cnta
			else:
				cnta += 1
		for i in range(len(t) - 1, post - 1, -1):
			if t[i] == 'D':
				res += cntb
			else:
				cntb += 1
		print(n * n - res)
main()


def solve():
	n = int(input())
	s = input()
	m = len(s)
	flag = True
	for i in range(1, m):
		if s[i] != s[i - 1]:
			flag = False
	if flag:
		return n
	(x, y) = (1, 1)
	for c in s:
		if c == 'R':
			y = y + 1
		if c == 'D':
			x = x + 1
	(x, y) = (n - x, n - y)
	res = m
	for i in range(m):
		if i and s[i] != s[i - 1]:
			flag = True
		if flag:
			if s[i] == 'R':
				res = res + x
			if s[i] == 'D':
				res = res + y
	return res + (x + 1) * (y + 1)
for i in range(int(input())):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	s = input()
	(posX, posY) = (0, 0)
	maxDown = [0]
	maxRight = [0]
	for c in s:
		if c == 'D':
			posY += 1
			maxDown[-1] += 1
			maxRight.append(posX)
		else:
			posX += 1
			maxDown.append(posY)
			maxRight[-1] += 1
	if posX == 0 or posY == 0:
		print(n)
	else:
		jeuBas = n - posY - 1
		jeuDroite = n - posX - 1
		nbCase = 0
		for i in maxDown:
			if i == 0:
				nbCase += n - 1
			else:
				nbCase += n - 1 - i - jeuBas
		for i in maxRight:
			if i == 0:
				nbCase += n - 1
			else:
				nbCase += n - 1 - i - jeuDroite
		print(n * n - nbCase)