Given a NxM matrix. Each cell of matrix contains pair of integers(x,y). Initially we are standing at cell (1,1). Find the minimum number of moves to reach the cell (N,M). If it is not possible return -1. So if we are at a cell (i,j) and pairs of integers at cell is (x,y) then you can move to cell (i+x,j+y),(i+x,j-y),(i-x,j+y),(i-x,j-y),(i+y,j+x),(i+y,j-x),(i-y,j+x) and (i-y,j-x). But you can't move outside matrix.

Constraints
1<=T<=10
1<=N,M<=1000
0<=x,y<=4

Input format:
First line contains numner of test cases T.
For each test case, first line will contain two spaced integers N,M number of rows and columns respectively.
Each of next N lines will have 2M spaced integers, pair of two integers from start will denote the value of x and y in each of the M cells in that row.

Example
T=1
N, M= 6, 5
2 0 2 2 0 0 1 2 2 1
2 0 0 2 1 2 1 2 0 2
0 1 0 2 1 0 1 1 2 0
2 2 0 1 2 2 1 1 1 1
0 1 1 2 0 2 1 0 1 2
2 1 0 0 1 1 1 1 0 1

Output: 5

Explanation:
The value of (x,y) in cell (1,1) is 2 and 0 respectively.
Similarly the value of x and y in (1,2) is 2 and 2 respectively.

for the above input one of the minimum path would be (1,1)->(3,1)->(3,2)->(3,4)->(4,3)->(6,5). So minimum moves would be 5.

How to solve this?