It's the 13th of July and it's Shubham Gupta's Birthday. Shubham loves to solve DP problem. Anuj (Shubham's friend) want to wish him uniquely. So he decorate their hostel room number 235 where the floor is divided into N × M square tiles, forming a grid with N rows and M columns.

Each square in the grid contains a number of vodka shots that Shubham has to drink if he steps on a particular tile. Shubham enters the room on (1, 1) and has to makes his way to the exit gate on (N, M), drinking the vodka on the way. From the current cell, he can move only to the adjacent cell in East, South or South-East direction i.e. from (i, j) to either (i, j+1) , (i+1, j) or (i+1, j+1).

However, his capacity for the vodka is limited. If he drink more than K shots, he will be out of control! Help him find a way to drink as any many shots as he can, without going out of control.

Input

The first line contains T. T test cases follow.
First line of each test case contains 3 space-separated integers, N, M, K.
Each of the following N lines contain M space-separated integers, describing the grid.

Output

Print the maximum number of vodka shots that he can drink without going out of control or "-1" (without the quotes) if it can not be done i.e. if there does not exist such a path. Print the answer to each test case on a new line. .

Constraints:

1 ≤ T ≤ 10
1 ≤ N, M ≤ 100
1 ≤ K ≤ 500
1 ≤ Values in the Grid ≤ 50

Example

Input:
2
3 3 7
2 3 1
6 1 9
8 2 3
3 4 9
2 3 4 1
6 5 5 3
5 2 3 4
Output:
6
-1

Explanation

In the first test case, he can move on squares (1, 1) , (2, 2) and (3, 3) to complete his journey with 6 shots. In the second test case, every possible path leads to the drinks of more than 9 shots.