L. 哈！昨日五次重现（简单版）

简单版和困难版的唯一区别是，在简单版中，$1\le T\le 10, 3\le n, m\le 15, X=Y=1$，且 $c=0$ 和 $c=1000$ 中恰有一个满足。

题目背景

2023 ICPC 南京站 A 题

南师学子参加 2023 ICPC南京站

在 2018、2020、2021、2022、2023 年的 ICPC 南京站中， SUA 命题组提出了五道与袋鼠相关的题目。

为了在济南站前热身， pzr 决定解决以下袋鼠谜题，你能帮帮他吗？

题目描述

给定一张 $n \times m$ 的网格，初始情况下，每个格子中有至多一只袋鼠（但是操作过程中，格子中可以容纳多个袋鼠）。除此之外，某一个特定格子 $(X, Y)$ 上将有一个洞。

接下来，你可以执行若干操作，每种操作是如下之一：

• 花费 $c$ 的代价，使得所有袋鼠 以洞的位置为中心 聚集，具体来说：
  • 位于洞正左方的格子中（位于同一行，但是列号小于洞所在列号）的所有袋鼠向右移动一格。
  • 位于洞正右方的格子中（位于同一行，但是列号大于洞所在列号）的所有袋鼠向左移动一格。
  • 位于洞正上方的格子中（位于同一列，但是行号小于洞所在行号）的所有袋鼠向下移动一格。
  • 位于洞正下方的格子中（位于同一列，但是行号大于洞所在行号）的所有袋鼠向上移动一格。
  • 位于洞左上方的格子中（行号小于洞所在行号，列号小于洞所在列号）的所有袋鼠向右移动一格、再向下移动一格。
  • 位于洞左下方的格子中（行号大于洞所在行号，列号小于洞所在列号）的所有袋鼠向右移动一格、再向上移动一格。
  • 位于洞右上方的格子中（行号小于洞所在行号，列号大于洞所在列号）的所有袋鼠向左移动一格、再向下移动一格。
  • 位于洞右下方的格子中（行号大于洞所在行号，列号大于洞所在列号）的所有袋鼠向左移动一格、再向上移动一格。
• 花费 $1$ 的代价，选择一只特定的袋鼠。
  • 将其移动到相邻（上、下、左、右）的四个格子之一。

当一只袋鼠掉入洞中，它将在网格中移除。如果在一系列操作后，恰有一只袋鼠留在网格中，则它成为最终赢家。

现在，假设你是某个位置 $(i, j)$ 的袋鼠，请你计算：至少需要花费多少代价，才能成为最终赢家？请对于每只袋鼠，求出答案 $c_1,c_2,\cdots ,c_k$。为了避免大量输出，你只需要求出各个答案的平方和，即 $\sum_{i=1}^k c_i^2$ 。

输入格式

第一行一个整数 $T$，表示测试数据组数。

接下来对于每组数据：

第一行五个整数 $n, m, c, X, Y$，分别表示网格的行数和列数，第一种操作的代价，以及洞所在位置。

接下来 $n$ 行每行一个长为 $m$ 的字符串，仅包含 $0$ 或 $1$，表示初始该格子中的袋鼠数量。保证洞所在位置一开始没有袋鼠。保证网格中至少有一只袋鼠。

输出格式

对于每组数据，仅一个非负整数，表示对于各袋鼠而言的最小代价的平方和。

样例输入1

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

样例输出1

10
148

样例1解释

对于第一组测试数据，聚集的代价为零，洞的位置在左上角（1,1）。

对于（1,2）的袋鼠，它需要先向右移动一步。

0010

1010

0100

接下来，将所有袋鼠向洞的方向聚集

0100

1200

0000

（2,1）的袋鼠将掉进洞中，（2,3）和（3,2）的袋鼠将聚集到（2,2）。

此时，它再向右移动一步。

0010

1200

0000

接下来，将所有袋鼠向洞的方向聚集

0100

0000

0000

总代价是 $2$。

同理，（2,1）处的总代价是 $2$，（2,3）处的总代价是 $1$，$(3,2)$ 处的总代价是 $1$。

故输出 $2^2+2^2+1^2+1^2=10$。

数据范围与约定

---

子任务 1（50分）：

$c=0$

---

子任务 2（50 分）：

$c=1000$

---

对于所有测试点：

$1\le T\le 10$

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

$X=1$，$Y=1$

$c=0$ 和 $c=1000$ 中恰有一个满足。

保证洞所在位置一开始没有袋鼠。保证整个网格中至少有一只袋鼠。

保证所有数据中 $n\times m$ 的和不超过 $5\times 10^3$。

可以证明，在现有的数据范围约定下，无论是哪一只袋鼠，都有可能成为最终赢家。

可以证明，在现有的数据范围约定下，答案一定在 $32$ 位整数可表示的范围内。