Chef recently saw the movie Matrix. He loved the movie overall but he didn't agree with some things in it. Particularly he didn't agree with the bald boy when he declared - There is no spoon. Being a chef, he understands the importance of the spoon and realizes that the universe can't survive without it. Furthermore, he is sure there is a spoon; he saw it in his kitchen this morning. So he has set out to prove the bald boy is wrong and find a spoon in the matrix. He has even obtained a digital map already. Can you help him?

Formally you're given a matrix of lowercase and uppercase Latin letters. Your job is to find out if the word "Spoon" occurs somewhere in the matrix or not. A word is said to be occurred in the matrix if it is presented in some row from left to right or in some column from top to bottom. Note that match performed has to be case insensitive. 

-----Input-----
The first line of input contains a positive integer T, the number of test cases. After that T test cases follow. The first line of each test case contains two space separated integers R and C, the number of rows and the number of columns of the matrix M respectively. Thereafter R lines follow each containing C characters, the actual digital map itself.

-----Output-----
For each test case print one line. If a "Spoon" is found in Matrix, output "There is a spoon!" else output "There is indeed no spoon!" (Quotes only for clarity).

-----Constraints-----

1 ≤ T ≤ 100

1 ≤ R, C ≤ 100

-----Sample Input-----
3
3 6
abDefb
bSpoon
NIKHil
6 6
aaaaaa
ssssss
xuisdP
oooooo
ioowoo
bdylan
6 5
bdfhj
cacac
opqrs
ddddd
india
yucky

-----Sample Output-----
There is a spoon!
There is a spoon!
There is indeed no spoon!

-----Explanation-----
In the first test case, "Spoon" occurs in the second row. In the second test case, "spOon" occurs in the last column.

Difficulty: interview

Starter code:

Solutions:
import sys

spoon = [ "SPOON", "spoon" ]

def main():
 try:
  tc=int(input())
  while tc>0:
   tc=tc-1
   [r,c] = input().split()
   r=int(r)
   c=int(c)
   k=0
   flag=0
   matrix=[0]*r
   i=0
   while i<r:
    matrix[i]=input()
    i=i+1
   
   #Check row wise
   for m in matrix:
    for s in m:
     if s==spoon[0][k] or s==spoon[1][k]:
      k=k+1
      if k==5:
       flag=1
       k=0
       break
     else:
      k=0
   
   if flag==1:
    print("There is a spoon!")
    continue
   
   #Check column wise
   i=0
   k=0
   while i<c:
    j=0
    while j<r:
     if matrix[j][i]==spoon[0][k] or matrix[j][i]==spoon[1][k]:
      k=k+1
      if k==5:
       flag=1
       k=0
       break
     else:
      k=0
     j=j+1
    i=i+1
   
   if flag==1:
    print("There is a spoon!")
    continue
   
   print("There is indeed no spoon!")
 
 except:
  return 0
main()


def check(L):
 for l in L:
  if "spoon" in "".join(l):
   return True
 return False

def change(r,c,L):
 n = []
 for x in range(c):
  t = []
  for q in range(r):
   t.append(L[q][x])
  n.append(t)
 return n

for case in range(eval(input())):
 r, c = list(map(int, input().strip().split()))
 
 m = []
 for row in range(r):
  m.append(list(input().lower().strip()))
 if check(m):
  print("There is a spoon!")
 else:
  m = change(r, c, m)
  if check(m):
   print("There is a spoon!")
  else:
   print("There is indeed no spoon!")
  
  


import string

t=0
try:
 t=int(input().strip())
except:
 pass
for _ in range(0,t):
 r,c=[int(j) for j in input().split()]
 a=[]
 flag=False
 m=""
 for q in range(0,r):
  ll=input().lower()
  a.append(ll)
  m=m+ll
  
 for q in a:
  if q.find("spoon")!=-1:
   flag = True
   break
 if not flag:
  q=0
  bb=(r-4)*c
  while q<bb:
   if m[q]=="s":
    ja=m[q]+m[q+c]+m[q+2*c]+m[q+3*c]+m[q+4*c]
    if ja=="spoon":
     flag=True
     break
   q+=1
 if flag:
  print("There is a spoon!")
 else:
  print("There is indeed no spoon!")


t=int(input().strip())
for i in range(t):
 R,C=list(map(int,input().strip().split()))
 hit=['']*R
 for j in range(R):
  hit[j]=input().strip().lower()
 found=False
 for w in hit:
  if w.find('spoon')!=-1:
   print('There is a spoon!')
   found=True
   break
 if not found:
  for i in range(C):
   new=''.join([x[i] for x in hit])
   if new.find('spoon')!=-1:
    print('There is a spoon!')
    found=True
    break
  if not found: print('There is indeed no spoon!')

   


import sys

t = int(input())

debug = 0

for x in range(t):
 row, col = list(map(int, sys.stdin.readline().split()))

 spoon = 0

 matrix = []
 for r in range(row):
  row_in = sys.stdin.readline().strip().lower()
  pos = row_in.find('spoon')
  if pos != -1:
   spoon = 1
  matrix.append(row_in)
 
 if spoon == 1:
  print("There is a spoon!")
  continue

 # If not found in row major form, then try the column major form
 for c in range(col):
  col_in = ''
  for r in range(row):
   col_in += matrix[r][c]

  pos = col_in.find('spoon')
  if pos != -1:
   spoon = 1

 if spoon == 1:
  print("There is a spoon!")
 else:
  print("There is indeed no spoon!")
 
 if debug == 1:
  print(spoon)
  print(matrix)


import sys

t = int(input())

debug = 0

for x in range(t):
 row, col = list(map(int, sys.stdin.readline().split()))

 spoon = 0

 matrix = []
 for r in range(row):
  row_in = sys.stdin.readline().strip().lower()
  pos = row_in.find('spoon')
  if pos != -1:
   spoon = 1
  matrix.append(row_in)
 

 # If not found in row major form, then try the column major form
 for c in range(col):
  col_in = ''
  for r in range(row):
   col_in += matrix[r][c]

  pos = col_in.find('spoon')
  if pos != -1:
   spoon = 1

 if spoon == 1:
  print("There is a spoon!")
 else:
  print("There is indeed no spoon!")
 
 if debug == 1:
  print(spoon)
  print(matrix)


import sys

T = int( sys.stdin.readline() )

while( T ):
 T -= 1
 ins = sys.stdin.readline().split()
 R = int( ins[0] )
 C = int( ins[1] )
 horiwords = []
 vertiwords = [' ']*C
 flag = False
 for i in range( R ):
  horiwords.append( sys.stdin.readline().lower() )
  if 'spoon' in horiwords[i]:
   flag = True

 if not flag:
  for i in range( C ):
   for j in range( R ):
    vertiwords[i] += horiwords[j][i]
   if 'spoon' in vertiwords[i]:
    flag = True
    break

 if( flag ):
  print( 'There is a spoon!' )
 else:
  print( 'There is indeed no spoon!' )


#Program question at: http://www.codechef.com/MARCH12/problems/SPOON

t = int(input())
while t>0:
 t-=1
 s = input().split()
 m = int(s[0]); n = int(s[1])
 ar = []; f = True
 for i in range(m):
  s = input().lower()
  if s.find('spoon') >=0:
   print('There is a spoon!')
   f = False
  ar.append(s)
 if not f: continue
 for i in range(n):
  s = ''
  for j in range(m):
   s += ar[j][i]
  if s.find('spoon') >= 0:
   print('There is a spoon!')
   f = False
   break
 if f: print('There is indeed no spoon!')


t = int(input())
spoon = "spoon"
while t>0:
 t -= 1
 x, y = list(map(int, input().split(" ")))
 inp = []
 done = False
 for i in range(x):
  inp.append(input().lower())
 if y>4:
  for i in range(x):
   if inp[i].find(spoon) != -1:
    print("There is a spoon!")
    done = True
    break
  if done:
   continue
 if x>4:
  for i in range(y):
   temp = ""
   for j in range(x):
    temp += inp[j][i]
   if temp.find(spoon) != -1:
    print("There is a spoon!")
    done = True
    break
  if done:
   continue
 print("There is indeed no spoon!")

t=int(input())
while t:
 t-=1
 r,c=list(map(int,input().split(" ")))
 l=['']*c
 flag=0
 while r:
  r-=1
  str = input()
  if 'spoon' in str.lower():
   flag=1
  else:
   j=0
   for char in list(str):
    l[j]+=char
    j+=1
 for str1 in l:
  if 'spoon' in str1.lower():
   flag = 1
   break
 if flag==1: print('There is a spoon!')
 if flag==0: print('There is indeed no spoon!')

t = eval(input())
for p in range(t):
 line = input().split()
 r,c = int(line[0]),int(line[1])
 matrix = []
 found = False
 for i in range(r):
  matrix.append(input().lower())
 for i in range(r):
  if(matrix[i].find("spoon") != -1):
   print("There is a spoon!")
   found = True
   break
 if(not found):
  for i in range(c):
   line = ""
   for j in range(r):
    line += matrix[j][i]
   #print line
   if(line.find("spoon") != -1):
    print("There is a spoon!")
    found = True
    break
 if(not found):
  print("There is indeed no spoon!")


t = eval(input())
for ti in range(t):
 x = [int(i) for i in input().split()]
 found = False
 a = []
 for i in range(x[0]):
  a.append(input().lower())
 for i in range(x[0]):
  if a[i].find("spoon") != -1:
   found = True
   break;
 if not found:
  for j in range(x[1]):
   str = ""
   for i in range(x[0]):
    str += a[i][j]
   if str.find("spoon") != -1:
    found = True
    break;
 if found:
  print("There is a spoon!")
 else:
  print("There is indeed no spoon!")

cases=int(input())
for i in range(cases):
 flag,lines=0,[]
 nums=input().split()
 r,c=int(nums[0]),int(nums[1])
 for j in range(r):
  lines.append(input().lower())
  if lines[j].find("spoon")>=0:
   flag=1
 for j in range(c):
  line=""
  for k in range(r):
   line+=lines[k][j]
  if line.find("spoon")>=0:
   flag=1
 if flag==1:
  print("There is a spoon!")
 else:
  print("There is indeed no spoon!")