F. Fraudulent Exam
time limit per test
3 seconds
memory limit per test
512 МБ
input
standard input
output
standard output

There is an exam being held at ETH. Chairs in the exam room are arranged in a grid of size $$$n \times m$$$, with the student sitting at the $$$(i,j)$$$ $$$(1 \leq i \leq n; 1 \leq j \leq m)$$$ position having IQ $$$a_{i,j}$$$.

Professors at ETHz have become aware that students sometimes cheat at exam. Cheating at exams always happens the same way. Some set of students $$$S = \{b_1, b_2, \dots, b_s\}$$$ decide before hand to cheat, but a set of students $$$S$$$ is only valid if two of the following conditions hold.

  1. Let $$$b_i$$$ and $$$b_j$$$ have the smallest and largest IQ respectively in $$$S$$$, then $$$|a_{b_i} - a_{b_j}| \leq k$$$. Since otherwise student $$$b_j$$$ won't feel that it is beneficial to cheat.
  2. For all pairs of students $$$(b_i, b_j)$$$ in $$$S$$$ they must be able to communicate. Two students $$$b_i$$$ and $$$b_j$$$ can communicate if there exists a sequence of students $$$c_1, c_2, \dots c_p$$$ in $$$S$$$ for $$$p \geq 2$$$, such that $$$c_1 = b_i$$$, $$$c_p = b_j$$$ and $$$c_z$$$ is adjacent to $$$c_{z+1}$$$ for $$$(1 \leq z \lt p)$$$. We say two students are adjacent if they sit next to each other in the exam (up, down, left, right).

The professors at ETHz have already published the seating arrangement, and it is to late to change it. But they wonder, what is the largest possible number of students cheating in one group.

Input

Each test contains multiple test cases.

The first line contain an integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, the number of test cases. The description of the $$$t$$$ test cases follows.

The first line of each teset case contains three integers $$$n, m, k$$$ $$$(1 \leq n,m \leq 600; 1 \leq k \leq 10^9)$$$.

Then $$$n$$$ lines follow, each line contains $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \dots a_{i,m}$$$ $$$(1 \leq a_{i,j} \leq 10^9)$$$, where $$$a_{i,j}$$$ is the IQ of the student sitting in the $$$i$$$-th row and $$$j$$$-th column.

It is guaranteed that over all test cases $$$\sum n \cdot m \leq 600\cdot 600$$$

Output

For each test case, print the largest possible number of students cheating in one group.

Example
Input
3
3 3 1
1 3 1
1 3 1
1 3 1
4 4 2
1 4 4 1
1 3 4 2
3 3 3 4
2 2 2 2
2 2 3
1 4
7 10
Output
3
13
2