Little T, who has recently been working in a biological laboratory, has encountered a major problem.

Due to a recent upgrade in the laboratory, his partitioned petri dish is a rectangular parallelepiped with dimensions $a \times b \times c$, where $a, b, c$ are all positive integers. For the convenience of experiments, it is divided into $a \times b \times c$ unit cubic regions, each with dimensions $1 \times 1 \times 1$. A unit cube is identified by $(i, j, k)$, where $1 \le i \le a$, $1 \le j \le b$, and $1 \le k \le c$.

This petri dish has not been used for a long time. Now, Little T has been asked by his supervisor to disinfect some of these unit cubic regions (each region can be disinfected repeatedly). Due to strict experimental requirements, he is required to use a specific reagent, F, for disinfection.

This reagent F is quite peculiar. Each time a rectangular region of size $x \times y \times z$ (consisting of $x \cdot y \cdot z$ unit cubes) is disinfected, it requires only $\min\{x, y, z\}$ units of reagent F. Reagent F is very expensive, which has stumped Little T. Please tell him the minimum number of units of reagent F required. (Note: $\min\{x, y, z\}$ denotes the minimum of $x, y,$ and $z$.)

Input

The first line of the input file contains a positive integer $D$, representing the number of data sets.

Following this are $D$ data sets. Each data set begins with three numbers $a, b, c$ representing the dimensions of the petri dish. This is followed by $a$ matrices, each with $b$ rows and $c$ columns, containing space-separated 0s and 1s. A 0 indicates that the corresponding unit cube does not require disinfection, and a 1 indicates that the corresponding unit cube requires disinfection. For example, if the element at the 2nd row and 3rd column of the 1st matrix is 1, it means the unit cube $(1, 2, 3)$ needs to be disinfected.

It is guaranteed that $a \cdot b \cdot c \le 5\,000$ and $D \le 3$.

Output

The output contains $D$ lines, each containing an integer representing the minimum number of units of reagent F required for the corresponding petri dish.

Examples

Input 1

1
4 4 4
1 0 1 1
0 0 1 1
0 0 0 0
0 0 0 0
0 0 1 1
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0

Output 1

3