거리 유지

당신은 악명 높은 TV 프로그램의 출연자다. 출연자는 보통 황당한 일을 하게 되는데, 당신도 예외가 아니다.

지금 눈앞에 색이 다른 큐브 여러 개가 한 줄로 놓여 있다. 진행자가 좋아하는 색을 발표하면, 당신은 그 색을 기준으로 줄이 아름다운 상태가 되도록 최대한 빨리 큐브를 재배열해야 한다.

큐브에 왼쪽부터 $1, 2, \ldots$ 번호를 붙인다. 색 $c$인 큐브가 $k$개 있고 그 위치가 $p_1 < p_2 < \ldots < p_k$라고 하자. 같은 색 큐브끼리 이웃한 간격이 모두 같으면, 즉 다음 식이 성립하면 줄은 색 $c$에 대해 아름다운 상태이다.

$p_2 - p_1 = p_3 - p_2 = \ldots = p_k - p_{k-1}$

$k \le 2$이면 줄은 색 $c$에 대해 아름다운 상태로 본다.

허용되는 연산은 다음 하나뿐이며, 횟수에 제한은 없다. 색이 서로 다른 큐브 두 개를 골라 위치를 맞바꾼다. 두 큐브가 꼭 이웃할 필요는 없다.

진행자가 좋아하는 색은 아직 모른다. 줄에 등장하는 모든 색에 대해 줄을 아름답게 만드는 데 필요한 최소 교환 횟수를 구하려고 한다.

첫 줄에 정수 $t$ ($1 \le t \le 2\,500$)가 주어진다. 테스트 케이스의 개수이다.

이어지는 $t$개의 줄에는 각각 빈 문자열이 아닌 소문자 영문 문자열이 주어진다. 왼쪽부터 큐브의 색을 나타낸다. 'a'는 amaranth, 'b'는 bittersweet, 'c'는 crimson을 뜻하며 이하 알파벳 순서로 색을 나타낸다. 모든 입력 문자열 길이의 합은 $250\,000$을 넘지 않는다.

입력 문자열마다 정수 수열을 출력한다. 줄에 등장하는 색을 'a'부터 'z'까지 순서대로 보면서, 각 색에 대해 줄을 그 색을 기준으로 아름답게 만드는 데 필요한 최소 교환 횟수를 출력한다.

예시에서 줄은 이미 crimson('c')에 대해 아름다운 상태이다. red('r')에 대해 아름답게 만들려면 1번 큐브와 3번 큐브를 교환하면 충분하다. 그러면 줄은 rvvrcvrvvr이 된다. vermilion('v')에 대해 아름답게 만들려면, 예를 들어 1번과 5번 큐브를 교환한 다음 2번과 7번 큐브를 교환하면 된다. 그러면 줄은 crrrvvvvvr이 된다.