C. Треугольники
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Gildong есть квадратная доска из $$$n$$$ строк и $$$n$$$ столбцов квадратных клеток, каждая клетка содержит одну цифру (от $$$0$$$ до $$$9$$$). Клетка на пересечении $$$j$$$-го столбца и $$$i$$$-й строки может быть описана как $$$(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$$$ цифр без пробелов. В $$$j$$$-й цифре $$$i$$$-й строки записана цифра клетки $$$(i, j)$$$. Каждая цифра представлена символом от $$$0$$$ до $$$9$$$.

Гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^6$$$.

Выходные данные

Для каждого набора входных данных, выведите строку из $$$10$$$ целых чисел. $$$i$$$-е из них должно быть равно максимальной площади, которую может получить Gildong, для $$$d = i-1$$$, умноженной на $$$2$$$.

Пример
Входные данные
5
3
000
122
001
2
57
75
4
0123
4012
3401
2340
1
9
8
42987101
98289412
38949562
87599023
92834718
83917348
19823743
38947912
Выходные данные
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)$$$, но это некорректно, потому что это не удовлетворяет условию, что хотя бы одна сторона треугольника должна быть параллельна стороне доски.