Its 13th of July and its 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 no. 235 where the floor is divided into N x 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 testcases follow.
First line of each testcase 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 testcase in 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 testcase, he can move on squares (1,1) , (2,2) and (3,3) to complete his journey with 6 Shots. In the second testcase, every possible path leads to the drinks of more than 9 Shots.