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: interview

Starter code:

Solutions:
# cook your dish here
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')

# cook your dish here
a = int(input())
for i in range(a):
 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
 # d={'L':0,'R':1,'U':2,'D':3}
 # l=[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')

# cook your dish here
# cook your dish here
t=int(input())
for i in range(t):
 s=input().split()
 n=int(s[0])
 m=int(s[1])
 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")


# cook your dish here
t=int(input())
for i in range(t):
 s=input().split()
 n=int(s[0])
 m=int(s[1])
 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")


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,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)
  else:
   if arr[1] < r:
    arr[1] = r

  if c<0:
   if arr[2] < abs(c):
    arr[2] = abs(c)
  else:
   if 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
   




t = int(input())


for _ in range(t):
 n,m = list(map(int,input().split()))
 s = input()
 flag = 0
 for i in range(n):
  for j in range(m):
   x = i
   y = j
   for k in s:
    if k == 'L':
     y-=1
    elif k == 'U':
     x-=1
    elif k == 'D':
     x+=1
    elif k == 'R':
     y+=1

    if x<0 or x>=n or y<0 or y>=m:
     break

   if 0<=x<=n-1 and 0<=y<=m-1:
    flag = 1
    break
  if flag == 1:
   break
 if flag == 1:
  print('safe')
 else:
  print('unsafe')








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")


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 #displacement from starting position
 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
 #print(u,d,l,r)
 if n>abs(u)+abs(d) and m>abs(l)+abs(r):
  print("safe")
 else:
  print("unsafe")