There is a rectangular grid of cells consisting of n rows and m columns.
You will place a robot on one of the grid cells and provide it with a command string s, consisting of characters ‘L’, ‘R’, ‘U’, ‘D’.
After being placed, the robot will follow the instructions of the command string, where 'L' corresponds moving to the left, 'R' towards the right, 'U' for moving up, and 'D' means down.

You have already selected the command string s, and are wondering if it is possible to place the robot in one of the grid cells initially and have it always stay entirely within the grid upon execution of the command string s.
Output “safe” if there is a starting cell for which the robot doesn’t fall off the grid on following command s, otherwise, output "unsafe".

-----Input-----

The first line of input will contain an integer T, the number of test cases.

Each test case will be on two lines. 

The first line will have two space separated integers n,m. 

The second line will have the command string s.

-----Output-----

For each test case, output "safe" (without quotes) or "unsafe" (without quotes) in a new line.

-----Constraints-----
-  1 ≤ T ≤ 1,000
-  1 ≤ n,m ≤ 10
-  1 ≤ |s| ≤ 10

-----Example-----
Input:
5
1 1
R
2 3
LLRU
3 2
LLRU
4 3
ULURUDRDLD
3 6
RURUR

Output:
unsafe
safe
unsafe
safe
safe

-----Explanation-----

For the first case, there is only one grid square, so we must place our robot there. When the robot follows the command, it'll fall off, so it is unsafe.

For the second case, we can place the robot on the bottom right grid square. Here is an image denoting the moves that the robot will make.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
test = int(input())
for _ in range(test):
	b = list(map(int, str(input()).split(' ')))
	c = str(input())
	li1 = [0]
	li2 = [0]
	for i1 in range(len(c)):
		if c[i1] == 'R':
			li1.append(li1[len(li1) - 1] + 1)
		elif c[i1] == 'L':
			li1.append(li1[len(li1) - 1] - 1)
		elif c[i1] == 'U':
			li2.append(li2[len(li2) - 1] + 1)
		else:
			li2.append(li2[len(li2) - 1] - 1)
	if max(li1) - min(li1) + 1 <= b[1] and max(li2) - min(li2) + 1 <= b[0]:
		print('safe')
	else:
		print('unsafe')


for u in range(int(input())):
	(n, m) = map(int, input().split())
	st = input()
	f = 0
	for i in range(n):
		for j in range(m):
			x = i
			y = j
			for k in range(len(st)):
				if st[k] == 'L':
					y = y - 1
				elif st[k] == 'R':
					y = y + 1
				elif st[k] == 'U':
					x = x - 1
				elif st[k] == 'D':
					x = x + 1
				if x >= 0 and x < n and (y >= 0) and (y < m):
					ll = 0
				else:
					break
			if x >= 0 and x < n and (y >= 0) and (y < m):
				f = 1
	if f == 1:
		print('safe')
	else:
		print('unsafe')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	(t1, t2, t3, t4) = (0, 0, 0, 0)
	(xp, xn, yp, yn) = (0, 0, 0, 0)
	(c1, c2) = (0, 0)
	for (i, x) in enumerate(s):
		if x == 'L':
			c1 -= 1
		elif x == 'R':
			c1 += 1
		elif x == 'U':
			c2 += 1
		else:
			c2 -= 1
		xp = max(xp, c1)
		xn = min(xn, c1)
		yp = max(yp, c2)
		yn = min(yn, c2)
	if abs(xp - xn + 1) <= m and abs(yp - yn + 1) <= n:
		print('safe')
	else:
		print('unsafe')


def is_safe(n, m, i, j, s):
	for k in s:
		if k == 'L':
			j -= 1
		if k == 'R':
			j += 1
		if k == 'U':
			i -= 1
		if k == 'D':
			i += 1
		if (i < 1 or i > n) or (j < 1 or j > m):
			return -1
	return 1
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	s = input()
	flag = 0
	(l, r, u, d) = (0, 0, 0, 0)
	for i1 in range(1, n + 1):
		for i2 in range(1, m + 1):
			res = is_safe(n, m, i1, i2, s)
			if res == 1:
				flag = 1
				break
		else:
			continue
		break
	if flag == 1:
		print('safe')
	else:
		print('unsafe')


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	command = input()
	maxL = 0
	maxR = 0
	hom = 0
	maxU = 0
	maxD = 0
	vem = 0
	for co in command:
		if co == 'L':
			hom += 1
		elif co == 'R':
			hom -= 1
		elif co == 'U':
			vem += 1
		else:
			vem -= 1
		if hom > maxL:
			maxL = hom
		if hom < maxR:
			maxR = hom
		if vem > maxU:
			maxU = vem
		if vem < maxD:
			maxD = vem
	if maxL - maxR < m and maxU - maxD < n:
		print('safe')
	else:
		print('unsafe')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(a, b) = ([0], [0])
	x = y = 0
	for i in s:
		if i == 'U':
			x -= 1
			a.append(x)
		elif i == 'D':
			x += 1
			a.append(x)
		elif i == 'L':
			y -= 1
			b.append(y)
		elif i == 'R':
			y += 1
			b.append(y)
	row = max(a) - min(a) + 1
	col = max(b) - min(b) + 1
	if row > n or col > k:
		print('unsafe')
	else:
		print('safe')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	ans = 'unsafe'
	for i in range(n):
		for j in range(m):
			(x, y) = (i, j)
			res = 1
			for k in s:
				if k == 'L':
					y -= 1
				elif k == 'U':
					x -= 1
				elif k == 'R':
					y += 1
				else:
					x += 1
				if x < 0 or x >= n or y < 0 or (y >= m):
					res = 0
					break
			if res:
				ans = 'safe'
				break
	print(ans)


t = int(input())
for l in range(t):
	(n, m) = list(map(int, input().split()))
	a = False
	s = input()
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			x = i
			y = j
			loulou = False
			for h in range(len(s)):
				if s[h] == 'L':
					y = y - 1
				elif s[h] == 'R':
					y = y + 1
				elif s[h] == 'U':
					x = x + 1
				else:
					x = x - 1
				if x < 1 or x > n or y < 1 or (y > m):
					loulou = True
					break
			if loulou == False:
				a = True
				print('safe')
				break
		if a == True:
			break
	if a == False:
		print('unsafe')


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	s = input()
	flag = False
	for i in range(n):
		for j in range(m):
			(x, y) = (i, j)
			c = True
			for k in s:
				if k == 'L':
					y -= 1
				elif k == 'U':
					x += 1
				elif k == 'D':
					x -= 1
				else:
					y += 1
				if x < 0 or x > n - 1 or y < 0 or (y > m - 1):
					c = False
					break
			if c:
				flag = True
				break
		if flag:
			break
	if flag:
		print('safe')
	else:
		print('unsafe')


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	s = input()
	r = c = 0
	arr = [0, 0, 0, 0]
	for i in s:
		if i == 'R':
			c += 1
		elif i == 'L':
			c -= 1
		elif i == 'U':
			r += 1
		elif i == 'D':
			r -= 1
		if r < 0:
			if arr[0] < abs(r):
				arr[0] = abs(r)
		elif arr[1] < r:
			arr[1] = r
		if c < 0:
			if arr[2] < abs(c):
				arr[2] = abs(c)
		elif arr[3] < c:
			arr[3] = c
	if arr[0] + arr[1] >= n or arr[2] + arr[3] >= m:
		print('unsafe')
	else:
		print('safe')
	r = c = 0


import math
t = int(input())
for test in range(t):
	(n, m) = list(map(int, input().split()))
	up = 0
	down = 0
	left = 0
	right = 0
	s = input()
	f = 0
	for i in s:
		if i == 'L':
			left += 1
			if right > 0:
				right -= 1
			if left == m:
				break
		if i == 'R':
			right += 1
			if left > 0:
				left -= 1
			if right == m:
				break
		if i == 'U':
			up += 1
			if down > 0:
				down -= 1
			if up == n:
				break
		if i == 'D':
			down += 1
			if up > 0:
				up -= 1
			if down == n:
				break
	if abs(down) < n and abs(up) < n and (abs(left) < m) and (abs(right) < m):
		print('safe')
	else:
		print('unsafe')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	(r, l, u, d) = (0, 0, 0, 0)
	(x, y) = (0, 0)
	for i in s:
		if i == 'U':
			y += 1
		elif i == 'D':
			y -= 1
		elif i == 'R':
			x += 1
		else:
			x -= 1
		if x > r:
			r = x
		elif x < l:
			l = x
		elif y > u:
			u = y
		elif y < d:
			d = y
	if n > abs(u) + abs(d) and m > abs(l) + abs(r):
		print('safe')
	else:
		print('unsafe')