Problem Statement:-

You are provided a matrix of size N*N with source position at (0,0) and destination at (N-1,N-1) in a 2D array. Some of the positions in the array 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. A sequence of 1s in the 2D array is connected if every 1 in the sequence is adjacent (the above or left neighbour) to the next 1 in the sequence.

For example, in the following matrix,

'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. You can either make movement towards right or down, i.e., from position (x,y), you 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 the input array 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 the source and the destination otherwise print "NOT POSSIBLE".

import java.util.*;
class TestClass {
public static int a[][];
public static int s[][];
public static int size=0;
public static void main(String args[] ) throws Exception {
Scanner sc=new Scanner(System.in);
int test_case=sc.nextInt();
for(int k=0;k<test_case;k++){
size=sc.nextInt();
//System.out.println(size);
a=new int[size][size];
s=new int[size][size];
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
a[i][j]=sc.nextInt();
//System.out.print(a[i][j]+"\t");
s[i][j]=0;
}
//System.out.println();
}
TestClass t=new TestClass();
boolean res=t.solve(0,0);
if(res){
System.out.println("POSSIBLE");
}else{
System.out.println("NOT POSSIBLE");
}
}
}
public boolean solve(int x,int y){
if(move(x,y)==false){
//System.out.println("NOT POSSIBLE");
return false;
}
return true;
}
public boolean move(int x,int y){
if(x==size-1&&y==size-1){
s[x][y]=1;
return true;
}
if(isSafe(x,y)==true){
s[x][y]=1;
if(move(x+1,y)){
//move(x+1,y);
return true;
}
if(move(x,y+1)){
//move(x+1,y);
return true;
}
s[x][y]=0;
return false;
}
return false;

}
public boolean isSafe(int x,int y){
return (x>=0 && y>=0 && x<size && y<size && a[x][y]==1);
}

}