Use Java

Prison Break John was a prisoner in Alcatraz. He was a witty and intelligent guy, who was confident of escaping prison. After few days of observation, he figured out that the prison consists of (NN) cells, i.e. the shape of prison was (NN) matrix. Few of the cells of the prison contained motion detectors. So, John planned that while escaping the prison he will avoid those cells containing motion detectors. Yet before executing his plan, John wants to know the total number of unique possible paths which he can take to escape the prison. Initially John is in cell (0, 0) while the exit of the prison is at cell (N-1, N-1) Help John to find the total number of unique possible paths to escape the prison avoiding the motion detectors. Note: John can move in four directions [if his current location is (X, Y), he can move to either (X+1, Y), (X-1, Y), (X, Y+1), (X, Y-1)]. If the first cell (0, 0) and the last cell (N-1, N-1) contain motion detectors, then John can't break out of the prison. INPUT: Take input from a file in1.txt. The first line contains number of test cases T. T test cases follow. The first line of each test case contains an integer N, (i.e. the size of the (NxN) matrix). The next N lines contain N space separated values either 0 or 1. 1 represents a cell containing motion detectors and 0 represents a cell containing no motion detectors. OUTPUT Output total number of unique possible paths which he can take to escape the prison. If John cannot break out of the prison then the answer is O Constraint 1ST s20 1sNs 20