After having fun with a certain contraption and getting caught, Evirir the dragon decides to put their magical skills to good use — warping reality to escape fast!

You are given a grid with $n$ rows and $m$ columns of non-negative integers and an integer $k$. Let $(i, j)$ denote the cell in the $i$-th row from the top and $j$-th column from the left ($1 \le i \le n$, $1 \le j \le m$). For every cell $(i, j)$, the integer $a_{i, j}$ is written on the cell $(i, j)$.

You are initially at $(1, 1)$ and want to go to $(n, m)$. You may only move down or right. That is, if you are at $(i, j)$, you can only move to $(i+1, j)$ or $(i, j+1)$ (if the corresponding cell exists).

Before you begin moving, you may do the following operation any number of times:

• Choose an integer $i$ between $1$ and $n$ and cyclically shift row $i$ to the left by $1$. Formally, simultaneously set $a_{i,j}$ to $a_{i,(j \bmod m) + 1}$ for all integers $j$ ($1 \le j \le m$).

Note that you may not do any operation after you start moving.

After moving from $(1, 1)$ to $(n, m)$, let $x$ be the number of operations you have performed before moving, and let $y$ be the sum of the integers written on visited cells (including $(1, 1)$ and $(n, m)$). Then the cost is defined as $kx + y$.

Find the minimum cost to move from $(1, 1)$ to $(n, m)$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line contains three space-separated integers $n$, $m$, and $k$ ($1 \leq n, m \leq 200$, $0 \leq k \leq 10^9$).

Then, $n$ lines follow. The $i$-th line contains $m$ space-separated integers, $a_{i,1},\,a_{i,2},\,\ldots,\,a_{i,m}$ ($0 \leq a_{i,j} \leq 10^9$).

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $5 \cdot 10^4$.

Output

For each test case, output a single integer, the minimum cost to move from $(1, 1)$ to $(n, m)$.

Note

In the first test case, the minimum cost of $113$ can be achieved as follows:

1. Cyclically shift row 3 once. The grid now becomes $$\begin{bmatrix}3 & 4 & 9\\5 & 2 & 4\\101 & 101 & 0\end{bmatrix}.$$
2. Move as follows: $(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (3, 3)$.

$x = 1$ operation is done before moving. The sum of integers on visited cells is $y = 3 + 4 + 2 + 4 + 0 = 13$. Therefore, the cost is $kx + y = 100 \cdot 1 + 13 = 113$.

In the second test case, one can shift row 1 once, row 2 twice, and row 3 thrice. Then, the grid becomes $$\begin{bmatrix}0 & 0 & 10 & 10\\10 & 0 & 0 & 0\\10 & 10 & 10 & 0\end{bmatrix}.$$

$x = 6$ operations were done before moving, and there is a path of cost $y = 0$. Therefore, the cost is $6 \cdot 1 + 0 = 6$.