你正在参加一个臭名昭著的电视节目。节目参与者通常会被要求做一些荒唐的事情，你也不例外。

现在，你面前有一排彩色方块。你的任务如下：节目主持人会宣布她最喜欢的颜色（该颜色在当前方块中存在）。然后，你必须尽快重新排列这些方块，使得这一行对于主持人最喜欢的颜色而言是“美丽的”。

我们将这一行中的方块从左到右编号为 $1, 2, \dots$。假设行中有 $k$ 个颜色为 $c$ 的方块，它们的位置分别为 $p_1 < p_2 < \dots < p_k$。如果该颜色相邻方块之间的距离相等，即满足以下等式：$p_2 - p_1 = p_3 - p_2 = \dots = p_k - p_{k-1}$，则称这一行对于颜色 $c$ 是“美丽的”。注意，如果 $k \le 2$，则该行对于颜色 $c$ 也是美丽的。

在重新排列方块的过程中，你只允许执行以下操作任意多次：取出任意两个颜色不同的方块并交换它们在行中的位置。注意，这两个方块不必相邻。

你已经看到了这一行方块，但你不知道主持人最喜欢的颜色。现在距离最终任务还有一些时间，你决定计算出使这一行对于每一种出现的颜色都变得“美丽”所需的最少交换次数。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 2500$)，表示测试用例的数量。

接下来的 $t$ 行，每行包含一个非空字符串，由小写英文字母组成，表示从左到右排列的方块颜色。其中，“a”代表 amaranth，“b”代表 bittersweet，“c”代表 crimson，以此类推。

输入字符串的总长度不超过 $250\,000$。

输出格式

对于每个输入行，输出一个整数序列。对于行中出现的每一种颜色（按“a”到“z”的顺序），输出使其对于该颜色变得“美丽”所需的最少交换次数。

样例

输入 1

1
vvrrcvrvvr

输出 1

0 1 2

说明

在样例测试用例中，该行对于深红色（“c”）已经是美丽的了。要使该行对于红色（“r”）变得美丽，只需交换第一个和第三个方块——此时该行将变为“rvvrcvrvvr”。要使该行对于朱红色（“v”）变得美丽，例如，只需交换第一个和第五个方块，然后交换第二个和第七个方块——此时该行将变为“crrrvvvvvr”。