Irene Adler is furious with Sherlock Holmes, as he is always busy with his work. So Sherlock decides to impress his lady love by buying her some gifts. He knows that he will have to buy at least K gifts. Miser that he is, he decides to go to the gift shop, and buy the cheapest K gifts available.

The shopkeeper on seeing the famous detective enter his shop, decides to test his intelligence. He organizes all the gifts in the shop in N lines, each line having M gifts. To further add to Sherlock’s misery, he encloses the gifts in each row in a transparent tube, and tells him that the gifts are accessible only from the ends i.e. he can only pick a gift only if there is no gift to its right or to its left. He asks Sherlock to pick one gift at a time and challenges him to minimize the total cost of the K gifts.

Sherlock, happy to have a challenge even in this boring task of buying gifts, accepts his challenge happily. Now he needs your help to pass the shopkeeper’s challenge and save some money. Given the cost of each gift in the N*M grid, find the minimum cost in which he can buy at least K gifts.

Input

The first line contains an integer T, the number of test cases.
The first line of each test case contains 3 integers N,M and K.
The next N lines contain M integer each, the cost of the items.

Constraints

1
1
1
1
1

Output

For each test case output a single line containing the minimum cost of K gifts.

Example

Input: 2 2 2 3 6 3 1 9 2 4 5 2 1 10 5 20 1 50 1 Output: 10 19