L. Ha, It's Yesterday Five Times More（Easy Version）

The only difference between the easy version and the hard version is that, in the easy version, $1 \leq T \leq 10$, $3 \leq n, m \leq 15$, $X=Y=1$, and exactly one of $c=0$ and $c=1000$ is satisfied.

Background

2023 ICPC Nanjing Site, Problem A The picture is not related to the description of the problem. If you cannot understand Chinese, feel free to skip it.

Students from Nanjing Normal University participate in the 2023 ICPC Nanjing Site.

In 2018, 2020, 2021, 2022, and 2023, the SUA problem-setting team proposed five problems related to kangaroos in the ICPC Nanjing Site.

To warm up before the Jinan Site, pzr decided to solve the following problem about kangaroos. Can you help him?

Description

Given an $n \times m$ grid, initially, each cell can have at most one kangaroo (but during the operation, a cell may contain multiple kangaroos). In addition, there's a hole in a specific cell $(X, Y)$.

You can perform several operations, each of which is one of the following:

• Cost $c$, causing all kangaroos to gather with the hole as the center, specifically:
  • All kangaroos in the cells to the left of the hole (in the same row but with column number less than the column number of the hole) move one cell to the right.
  • All kangaroos in the cells to the right of the hole (in the same row but with column number greater than the column number of the hole) move one cell to the left.
  • All kangaroos in the cells above the hole (in the same column but with row number less than the row number of the hole) move one cell down.
  • All kangaroos in the cells below the hole (in the same column but with row number greater than the row number of the hole) move one cell up.
  • All kangaroos in the cells to the top-left of the hole (with row number less than the row number of the hole and column number less than the column number of the hole) move one cell to the right and then one cell down.
  • All kangaroos in the cells to the bottom-left of the hole (with row number greater than the row number of the hole and column number less than the column number of the hole) move one cell to the right and then one cell up.
  • All kangaroos in the cells to the top-right of the hole (with row number less than the row number of the hole and column number greater than the column number of the hole) move one cell to the left and then one cell down.
  • All kangaroos in the cells to the bottom-right of the hole (with row number greater than the row number of the hole and column number greater than the column number of the hole) move one cell to the left and then one cell up.
• Cost $1$, choosing a specific kangaroo.
  • Move it to one of the four adjacent cells (up, down, left, right).

When a kangaroo falls into the hole, it will be removed from the grid. If after a series of operations, exactly one kangaroo remains in the grid, it becomes the final winner.

Now, assuming you are a kangaroo at position $(i, j)$, please calculate: What is the minimum cost to become the final winner? For each kangaroo, find the answers $c_1, c_2, \ldots, c_k$. To avoid excessive output, you only need to find the sum of the squares of the individual answers, i.e., $\sum_{i=1}^k c_i^2$.

Input Format

The first line contains an integer $T$, representing the number of test cases.

For each test case:

The first line contains five integers $n, m, c, X, Y$, representing the number of rows and columns of the grid, the cost of the first operation, and the position of the hole.

Next, there are $n$ lines, each containing a string of length $m$, consisting of only $0$ or $1$, indicating the initial number of kangaroos in that cell. It's guaranteed that there are no kangaroos at the hole's initial position. It's guaranteed that there is at least one kangaroo in the entire grid.

Output Format

For each test case: Only one non-negative integer, representing the sum of the squares of the minimum costs for each kangaroo.

Sample Input 1

2
3 4 0 1 1
0100
1010
0100
3 4 1000 1 1
0100
1010
0100

Sample Output 1

10
148

Sample 1 Explanation

For the first test case, the cost of aggregation operations is zero, and the hole is located at the top-left corner (1,1).

For the kangaroo at (1,2), it needs to move right by one step.

0010 1010 0100

Next, all kangaroos are gathered towards the hole.

0100 1200 0000

The kangaroo at (2,1) falls into the hole, and the kangaroos at (2,3) and (3,2) gather at (2,2).

At this point, it moves right by one step again.

0010 1200 0000

Next, all kangaroos are gathered towards the hole.

0100 0000 0000

The total cost is $2$.

Similarly, the total cost at (2,1) is $2$, at (2,3) is $1$, and at (3,2) is $1$.

Hence, the output is $2^2+2^2+1^2+1^2=10$.

Data Range and Constraints

---

Subtask 1 (50 points):

$c=0$

---

Subtask 2 (50 points):

$c=1000$

---

For all test cases:

$1\le T\le 10$

$3\le n,m\le 15$，$n+m>6$。

$X=1$，$Y=1$

Exactly one of $c=0$ and $c=1000$ is satisfied.

It's guaranteed that there are no kangaroos initially at the hole's position. It's guaranteed that there is at least one kangaroo in the entire grid.

It's guaranteed that the sum of $n \times m$ in all test cases does not exceed $5 \times 10^3$.

It can be proved that under the current constraints, any kangaroo can become the final winner.

It can be proved that under the current constraints, the answer must be representable by a $32$-bit integer.

The English Version of the Statement is Translated By ChatGPT.