To defend his castle Count Takeshi has invented a new challenge. In this challenge, the participant goes to a room that has n corridors and each corridor has n cells. Each cell has some coins of gold in it i.e. the jth cell of the ith corridor has a[i][j] gold coins ( 1<=i<=n && 1<=j<=n).

The participant starts at the cell [1][1] and ends at the cell [N][N]. Therefore, a[1][1]=a[N][N]=0.  He may move either to the cell directly in front of him on the same corridor or to the cell in the next corridor directly in front of where he is. In other words, if the participant is present at cell [i][j] he may move to [i+1][j] or to [i][j+1] . That is , he cannot go back. Also he cannot go out of the grid of cells.
 
When the participant arrives at the cell [N][N] he has to give the guard atleast C number of coins otherwise he will not be able to pass. Your job is to find out what is the  maximum number of coins the participant is left with after he passes the final guard.

Input:

The first line contains a single integer T denoting the number of test cases. The description for T test cases follows. For each test case, the first line contains  integers n and c. Each of the next n lines contains n space-separated integers.
The j-th integer a[i][j] in i-th line denotes the number of coins at the cell [i][j].

Output:

For each test case output a single line containing the the maximum number of coins the participant Is left with after he passes the final guard. If he doesn’t have sufficient number of coins output -1;

Constraints:

1 <= T <= 20

2 <= N <= 100

0 <= a[i][j] <= 2500

a[1][1] = a[N][N] = 0

SAMPLE TEST CASES:

Input:

2

2 7

0 0

8 0

2 5

0 1

3 0

Output:

1

-1