Find Longest Sequence

You are given a ‘N’ * ‘N’ matrix where all numbers are distinct from (1 to N * N). You are required to find the maximum length path (starting from any cell) such that all cells along the path are in increasing order with a difference of 1.

Only four possible movements are allowed i.e, Up, Down, Left , and Right.

For example :

Input:  Mat [ ][ ] = { { 9 , 1 , 3 }
                       { 7 , 4 , 2 }
                       { 6 , 5 , 8 } }
Output: 4
Explanation: The longest path is of length ‘4’ { 4 - 5 - 6 - 7 }

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains a single integer 'N' denoting the size of the matrix as N*N.
‘N’ lines follow. Each of the next ‘N’ lines contains ‘N’ space separated integers separated by space.

Output Format:

For each test case, return an integer denoting the maximum length path.
Output for each test case should be printed in a separate line.

Note

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 100   
1 <= N <= 10^3

Time Limit : 1 sec