Problem: Arya Stark a headstrong, fiercely independent, disdains traditional women's pursuits, the younger daughter of Lord Eddard Stark and his wife Lady Catelyn Starkand who is often mistaken for a boy, becomes increasingly hardened and brutalized, and personally kills a number of men after the execution of her father. She compiles a list of people she intends to kill.
Chiswyck - For capturing them, for thinking that Polliver taking her Needle was funny.
Dunsen - For capturing them, for taking Gendry's bull's horn helmet
Ser Meryn Trant - For killing Syrio Forel
Today, while working her routine she manages to cross another villain off her list "Ser Meryn Trant", the cruelest member of the Kingsguard, who she blames for killing Syrio Forel, the man hired by Ned Stark to train her with a swordand later had a hand in Ned Stark’s execution.
But like always it's not an easy task.
Little Arya is on the one corner of the hallway and Ser Meryn Trant on the diagonaly opposite corner. There is a little trick in the hallway of House of Black and White. Little Arya can jump only on white tile and move but can't jump on black tile,if she jumps Ser Meryn Trant will flew away.The hallway is of size N*N with source position of Arya as (0,0) and Ser Meryn Trant as (N-1,N-1) in the hallway. There are combination of white and black tiles ,the black ones are marked as 0 which are blocked cells, rest being marked 1.

A path is a connected sequence of elements from (0,0) to (N-1,N-1) which consists of 1 for arya to execute. A sequence of 1s in the hallway is connected if every 1 in the sequence is adjacent (the above or left neighbour) to the next 1 in the sequence.

For example,

'1' '1' '0'

'0' '1' '1'

'1' '0' '1'

the 1s marked in quotes is a connected path from (0,0) to (2,2)

Note that cells at (0,0) and (N-1,N-1) are always 1. she can either make movement towards right or down, i.e., from position (x,y) she can go to either the position (x,y+1) or (x+1,y).

Input

First line consists of the number of test cases and second line consist of size of hallway (N ≤ 50), following that would be the state of NxN maze which would consist of 0s and 1s.

Output

You have to print "POSSIBLE" if there exists a path between Arya and the Ser Meryn Trant, otherwise print "NOT POSSIBLE".

SAMPLE INPUT
2
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
3
1 0 0
0 0 0
0 0 1

SAMPLE OUTPUT
POSSIBLE
NOT POSSIBLE

Solution (in PYTHON):

Solution:
def path(a,x,y,goal):
	c=0
	if(x==goal and y==goal):return 1
	
	if(x==n-1 and a[x][y+1]==1):c= path(a,x,y+1,goal)
	
	if(c==0 and y==n-1 and a[x+1][y]==1):c= path(a,x+1,y,goal)
	
	if(c==0 and x<n-1 and a[x+1][y]==1):c= path(a,x+1,y,goal)
	
	if(c==0 and y<n-1 and a[x][y+1]==1):c= path(a,x,y+1,goal)
	
	return c
	
t=input()
for _ in xrange(t):
	n=input()
	a=[]
	for __ in xrange(n):
		a.append(map(int,raw_input().split()))
	c=path(a,0,0,n-1)
	if c==0:print "NOT POSSIBLE"
	else:print "POSSIBLE"