Minimal Operations

For each lowercase English word, you may replace any character with any lowercase letter; find the minimum number of replacements needed so that all adjacent characters differ. Output the result for each word independently.

输入格式

The input gives the number of words n and n lines of words. The full original bounds are kept: 1≤n≤100, each word has length 2..100000, and the characters are a..z; no total-length constraint is added to shrink the input, so the total number of characters can reach 10000000.

输出格式

Output the minimum number of replacements for each word in input order, separated by spaces or newlines.

样例 1

输入：

3
add
boook
break

输出：

1 1 0

样例 2

输入：

5
ab
aab
abb
abab
abaaaba

输出：

0 1 1 0 1

样例 3

输入：

2
zz
zzzzzz

输出：

1 3

样例说明

The outputs of the three public examples are, in order: 1 1 0; 0 1 1 0 1; 1 3. They have been checked by independent enumeration or direct simulation.