Карыч забыл что-то очень важное и сильно обеспокоился из-за этого. Смешарики решили ему помочь.
Они подключили Карыча к компьютеру Лосяша и обнаружили $$$n$$$ воспоминаний $$$s_1, s_2, \ldots, s_n$$$, представленных в виде строк.
Карыч может переместиться из воспоминания $$$s_i$$$ в воспоминание $$$s_j$$$, если существует такой символ $$$c$$$, что $$$f(s_i, c) \gt 0$$$ и $$$f(s_i, c) = f(s_j, c)$$$, где $$$f(s, c)$$$ — количество вхождений символа $$$c$$$ в строку $$$s$$$. После такого перемещения компьютер Лосяша нагреется на $$$f(s_i, c)$$$ градусов. Если возможных перемещений несколько, Карыч может выбрать любое.
Расстоянием от воспоминания $$$s_i$$$ до воспоминания $$$s_j$$$ называется суммарный нагрев компьютера Лосяша на пути Карыча от $$$s_i$$$ к $$$s_j$$$.
Карыч забыл, какое из воспоминаний является важным. Помогите ему определить минимальное расстояние от первого воспоминания до всех остальных. Если до каких-то воспоминаний добраться невозможно, определите это.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора дано целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество воспоминаний.
В следующих $$$n$$$ строках даны воспоминания $$$s_1, s_2, \ldots, s_n$$$, состоящие из строчных букв латинского алфавита.
Гарантируется, что сумма длин $$$s_i$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите $$$n - 1$$$ целых чисел — минимальные расстояния до воспоминаний $$$s_2, s_3, \ldots, s_n$$$ соответственно. Если какое-то воспоминание недостижимо, выведите вместо минимального расстояния «-1».
32ulyanovskisthebestmoscowisthebest2abcdefgh5ullllyyyyyyaaaaaaaannnnnnnnnnovsk
1-12 5 9 14
