The Professor is facing the North. Tokyo is in trouble, and she is facing the South. Professor being her guardian angel wants to help her.

So, The Professor will follow some instructions, given as a string S of length N, and will turn either left or right according to these instructions. He can save Tokyo only if after following a [substring] of instructions he will face in the same direction that Tokyo is facing. 

Will the Professor be able to save Tokyo?

------ Input Format ------ 

- The first line contains an integer T denoting the number of test cases. The T test cases then follow.
- The first line of each test case contains N.
- The second line contains a string that contains only 'L' and 'R', where 'L' represents left and 'R' represents right.

------ Output Format ------ 

For each test case, output "YES" if the Professor will be able to save Tokyo and "NO" otherwise.

Output is case insensitive, which means that "yes", "Yes", "YEs", "no", "nO" - all such strings will be acceptable.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10^{5}$
- The string $S$ consists of uppercase characters 'L' and 'R' only.
- The sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
3
12
LRLRRRLRLLLL
2
LR
4
LRRL

----- Sample Output 1 ------ 
YES
NO
YES

----- explanation 1 ------ 
Test case $1$: Professor can select the substring "RLRLLL", after following the instructions given by it, Professor will face South.

Test case $2$: No matter which substring Professor selects, the final direction of Professor will never be that in which Tokyo is facing.

Difficulty: MEDIUM
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	direction = input()
	pairs = [direction[i:i + 2] for i in range(n - 1)]
	for pair in pairs:
		if pair == 'LL' or pair == 'RR':
			print('YES')
			break
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	direction = input()
	flag = 0
	for i in range(n - 1):
		if direction[i] == 'L' and direction[i + 1] == 'L' or (direction[i] == 'R' and direction[i + 1] == 'R'):
			print('YES')
			flag = 1
			break
	if flag == 0:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	if 'RR' in s:
		print('YES')
	elif 'LL' in s:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	thing = input()
	thingy = input()
	if 'RR' in thingy:
		print('YES')
	elif 'LL' in thingy:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if s.find('RR') != -1 or s.find('LL') != -1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	if 'LL' in s or 'RR' in s:
		print('YES')
	else:
		print('NO')


def has_consecutive_letters(s):
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			return True
	return False
for _ in range(int(input())):
	n = int(input())
	s = input()
	print('YES' if has_consecutive_letters(s) else 'NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	if 'LLL' in s or 'RR' in s:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	n = int(input())
	direc = input()
	flag = 0
	for i in range(n - 1):
		if direc[i] == direc[i + 1]:
			flag = 1
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')
	t = t - 1


drc = 'north'
dic = {'north': ['east', 'west'], 'south': ['west', 'east'], 'east': ['south', 'north'], 'west': ['north', 'south']}
for i in range(int(input())):
	n = int(input())
	st = input()
	drc = 'north'
	for i in range(n - 1):
		if st[i] == 'R' and st[i + 1] == 'R' or (st[i] == 'L' and st[i + 1] == 'L'):
			print('YES')
			break
	else:
		print('NO')


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	s = input()
	if 'LL' in s or 'RR' in s:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	flag = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			flag = 1
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	x = input()
	flag = 0
	for i in range(len(x) - 1):
		if x[i] == x[i + 1]:
			flag = 1
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = input()
	f = 0
	for i in range(n - 1):
		if l[i] == l[i + 1]:
			f = 1
			break
	if f:
		print('YES')
	else:
		print('NO')


x = int(input())
hj = {'N': ['W', 'E'], 'E': ['N', 'S'], 'W': ['S', 'N'], 'S': ['E', 'W']}
rt = []
for im in range(0, x):
	frt = int(input())
	pl = str(input())
	rt.append(pl)
for nnb in rt:
	start = 'N'
	op = 0
	thy = 0
	while thy < len(nnb):
		upo = hj[start]
		if nnb[thy] == 'L':
			start = upo[0]
		else:
			start = upo[1]
		if start == 'N':
			continue
		if start == 'S':
			op = 1
			print('YES')
			break
		thy += 1
	if op == 0:
		print('NO')


for _ in range(int(input())):
	a = int(input())
	st = input()
	if 'LL' in st or 'RR' in st:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	string = []
	Sum = 0
	directions = input()
	if 'LL' in directions or 'RR' in directions:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	k = int(input())
	l = input()
	if 'LL' in l or 'RR' in l:
		print('YES')
	else:
		print('NO')


import re
for i in range(int(input())):
	n = int(input())
	seq = input()
	if n == 1 or n == 0:
		print('NO')
	else:
		list1 = re.findall('L{2}', seq)
		list2 = re.findall('R{2}', seq)
		if len(list1) > 0 or len(list2) > 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	i = int(input())
	ans = 'NO'
	j = list(input())
	for val in range(i - 1):
		if j[val] == j[val + 1]:
			ans = 'YES'
			break
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	a = 0
	for i in range(n - 1):
		if s[a:a + 2] == 'LR' or s[a:a + 2] == 'RL':
			a += 1
			continue
		else:
			print('YES')
			break
	else:
		print('NO')


for _ in range(int(input())):
	N = int(input())
	S = input()
	answ = 'NO'
	for i in range(1, len(S)):
		if S[i] == S[i - 1]:
			answ = 'YES'
			break
	print(answ)


n = int(input())
for i in range(n):
	l = int(input())
	s = input()
	if 'RR' in s or 'LL' in s:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	length = int(input())
	word = input()
	if 'LL' in word or 'RR' in word:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	N = int(input())
	string = str(input())
	flag = 0
	for x in range(N):
		if string[x] == 'L' and string[x - 1] == 'L':
			flag = 1
		elif string[x] == 'R' and string[x - 1] == 'R':
			flag = 1
	if flag:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	for i in range(1, n):
		if s[i] == s[i - 1]:
			print('YES')
			break
	else:
		print('NO')


def t():
	n = int(input())
	arr = list(input())
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			return 'YES'
	return 'NO'
for i in range(int(input())):
	print(t())


def solve(n, s):
	for i in range(1, n):
		if s[i] == 'L' and s[i - 1] == 'L':
			return 'YES'
		if s[i] == 'R' and s[i - 1] == 'R':
			return 'YES'
	return 'NO'
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(solve(n, s))


try:
	for _ in range(int(input())):
		n = int(input())
		s = input()
		flag = 0
		for i in range(len(s)):
			if s[i] == 'L' and s[i - 1] == 'L':
				flag = 1
			if s[i] == 'R' and s[i - 1] == 'R':
				flag = 1
		if flag:
			print('YES')
		else:
			print('NO')
except:
	pass


for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in range(n - 1):
		if s[i] == 'L' and s[i + 1] == 'L' or (s[i] == 'R' and s[i + 1] == 'R'):
			c = 1
			break
	if c == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = s.count('LL')
	r = s.count('RR')
	if l == 0 and r == 0:
		print('NO')
	else:
		print('YES')


t = int(input(''))
for i in range(t):
	n = int(input(''))
	s = input()
	ans = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			ans = 1
			break
	if ans == 1:
		print('YES')
	else:
		print('NO')


t = input()
for c in range(0, int(t)):
	N = int(input())
	S = input()
	for i in range(1, N):
		if S[i] == S[i - 1]:
			print('YES')
			break
	else:
		print('NO')


for _ in range(int(input())):
	N = int(input())
	S = input()
	for i in range(1, N):
		if S[i] == S[i - 1]:
			print('YES')
			break
	else:
		print('NO')


for _ in range(int(input())):
	N = int(input())
	A = input()
	flag = False
	for i in range(1, N):
		if A[i - 1] == 'L' and A[i] == 'L' or (A[i - 1] == 'R' and A[i] == 'R'):
			flag = True
			break
	if flag == True:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	N = int(input())
	A = input()
	for i in range(1, N):
		if A[i - 1:i + 1] == 'LL':
			print('YES')
			break
		elif A[i - 1:i + 1] == 'RR':
			print('YES')
			break
	else:
		print('NO')


for _ in range(int(input())):
	N = int(input())
	A = input()
	for i in range(1, N):
		if A[i - 1] == 'L' and A[i] == 'L':
			print('YES')
			break
		elif A[i - 1] == 'R' and A[i] == 'R':
			print('YES')
			break
	else:
		print('NO')


get_int = lambda : int(input())
get_mint = lambda : list(map(int, input().split()))
for _ in range(get_int()):
	N = get_int()
	S = input()
	direction = 0
	for i in range(N - 1):
		if S[i] == S[i + 1]:
			direction = 1
	if direction:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	n = int(input())
	s = input()
	x = 'LL'
	y = 'RR'
	t = t - 1
	if x in s or y in s:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	ans = 'NO'
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			ans = 'YES'
			continue
	print(ans)


from sys import stdin, stdout
stdint = lambda : int(stdin.readline())
stdstr = lambda : stdin.readline().strip()
for _ in range(stdint()):
	n = stdint()
	s = stdstr()
	if 'RR' in s or 'LL' in s:
		print('YES')
	else:
		print('NO')