Gildong 有一个方形板,由 $$$n$$$ 行和 $$$n$$$ 列方形单元格组成,每个单元格由一个数字组成(从 $$$0$$$ 到 $$$9$$$)。第$$$i$$$行第$$$j$$$列的单元格可以表示为$$$(i,j)$$$,每个单元格的边长为$$$1$$$。 Gildong 喜欢大的东西,所以对于每个数字 $$$d$$$,他想找到一个三角形,使得:
- 三角形的每个顶点都位于单元格的中心。
- 三角形每个顶点的数字是$$$d$$$。
- 三角形的至少一侧与棋盘的一侧平行。您可以假设长度为 $$$0$$$ 的边与板的两侧平行。
- 三角形面积最大化。
当然,他不能仅仅满足于按原样找到这些三角形。因此,对于每一个数字$$$d$$$,他要把棋盘上一个单元格的数字改为$$$d$$$,然后找到这样一个三角形。当他完成每个数字后,他将其改回原来的数字。求他能为每个数字画出的三角形的最大面积。
注意,他可以将三角形的多个顶点放在同一个单元格上,并且该三角形可以是退化三角形;即三角形的面积可以是$$$0$$$。另请注意,他可以将单元格的数字从 $$$d$$$ 更改为 $$$d$$$。
输入
每个测试都包含一个或多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2000$$$) — 棋盘的行数和列数。
每个测试用例的接下来的 $$$n$$$ 行均包含一串不带空格的 $$$n$$$ 数字。第 $$$i$$$ 行的第 $$$j$$$ 数字是 $$$(i, j)$$$ 处单元格的数字。每个数字都是从 $$$0$$$ 到 $$$9$$$ 的字符之一。
保证所有测试用例中$$$n^2$$$的总和不超过$$$4 \cdot 10^6$$$。
输出
对于每个测试用例,打印一行包含 $$$10$$$ 整数。第$$$i$$$个整数是当$$$d = i-1$$$时Gildong可以制作的三角形的最大面积,乘以$$$2$$$。
示例
输入 #1
5 3 000 122 001 2 57 75 4 0123 4012 3401 2340 1 9 8 42987101 98289412 38949562 87599023 92834718 83917348 19823743 38947912
输出 #1
4 4 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 9 6 9 9 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 49 49 49 49 15 0 30 42 42
注意
在第一种情况下,对于 $$$d=0$$$,无论他选择使用哪个单元格,顶点为 $$$(1, 1)$$$、$$$(1, 3)$$$ 和 $$$(3, 1)$$$ 的三角形都是面积为 $$$\cfrac{2 \cdot 2}{2} = 2$$$ 的最大三角形。由于我们应该打印它乘以 $$$2$$$,因此 $$$d=0$$$ 的答案是 $$$4$$$。
对于 $$$d=1$$$,Gildong 可以将 $$$(1, 3)$$$ 处的单元格数字更改为 $$$1$$$,从而制作一个三角形,其顶点位于所有三个 $$$1$$$ 上,面积为 $$$2$$$。
对于$$$d=2$$$,Gildong可以将以下六个单元格之一的数字更改为$$$2$$$,以形成面积为$$$\cfrac{1}{2}$$$的三角形:$$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(3, 1)$$$、$$$(3, 2)$$$ 和 $$$(3, 3)$$$。
对于剩余的数字(从 $$$3$$$ 到 $$$9$$$),Gildong 选择更改的单元格将是包含该数字的唯一单元格。因此,三角形将始终是面积为 $$$0$$$ 的退化三角形。
在第三种情况下,对于 $$$d=4$$$,请注意,如果 Gildong 更改 $$$(1, 4)$$$ 处单元格的数字并将其与 $$$(2, 1)$$$ 和 $$$(4, 3)$$$ 处的单元格一起使用,则三角形将比答案更大,但这是无效的,因为它违反了三角形的至少一侧必须平行于其中之一的条件板的两侧。