You are given an integer $k$ and a matrix $v$ with $n$ rows and $m$ columns. The element in row $i$ and column $j$ is denoted by $v_{i,j}$.

A cell $(x, y)$ is called a peak if its value is greater than or equal to the sum of the values in all other cells in row $x$ and column $y$. Formally, $(x, y)$ is a peak if

$$ v_{x,y} \ge \sum_{\substack{1 \le i \le n \\i \neq x}} v_{i,y} + \sum_{\substack{1 \le j \le m \\j \neq y}} v_{x,j}. $$

You may perform the following operation any number of times (possibly zero):

• Choose four integers $x_l$, $x_r$, $y_l$, and $y_r$ ($1 \le x_l \le x_r \le n$, $1 \le y_l \le y_r \le m$).
• Subtract $1$ from $v_{i,j}$ for every $x_l \le i \le x_r$ and $y_l \le j \le y_r$.

Find the minimum number of operations required to obtain a matrix with at least $k$ peaks.

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 of each test case contains three integers $n$, $m$, and $k$ ($1 \le n, m \le 10^5$, $1 \le k \le n \cdot m$, $n \cdot m \le 10^5$) — the number of rows, the number of columns, and the required number of peaks.

The $i$-th of the next $n$ lines contains $m$ integers $v_{i,1}, v_{i,2}, \ldots, v_{i,m}$ ($-10^9 \le v_{i,j} \le 10^9$).

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

Output

For each test case, output a single integer — the minimum number of operations required to obtain at least $k$ peaks.

If there is no solution, print a single integer $-1$.

Note

For the first test case, you can perform the following two operations:

• choose $(x_l, x_r, y_l, y_r) = (1, 3, 2, 3)$;
• choose $(x_l, x_r, y_l, y_r) = (2, 3, 1, 3)$.

After these operations, the matrix will be:

$\color{green}{-1}$$-31$$\color{green}{6}$$5$$\color{green}{-5}$$\color{green}{20}$$\color{green}{0}$$\color{green}{-20}$$\color{green}{14}$

The seven peaks are highlighted in green. For example:

• The cell $(1, 1)$ is a peak because $-1 \ge 5 + 0 - 31 + 6 = -20$;
• The cell $(3, 1)$ is a peak because $0 \ge -20 + 14 - 1 + 5 = -2$;
• The cell $(2, 1)$ is not a peak because $5 \lt -5 + 20 - 1 + 0 = 14$.

It can be shown that fewer than two operations cannot create seven peaks, so the answer is $2$.

In the eighth test case, the only cell has value $-5$. A cell in a $1 \times 1$ matrix is a peak if and only if its value is non-negative. Since every operation only decreases its value, it is impossible to make it a peak.

For the last test case, both cells are peaks exactly when their values are equal. Therefore, the first cell must be decreased from $10^9$ to $-10^9$, which requires $2 \cdot 10^9$ operations.