No Pairs Allowed

For each word in words, compute separately the minimum number of character replacements so that the result has no two equal adjacent characters. Each replacement changes the letter at one position; you do not need to output the modified words.

The full original ranges are kept; this site only wraps the standard input/output.

输入格式

The first line contains n; each of the next n lines contains a lowercase ASCII word. Full original ranges: 1≤n≤100, 2≤(length of each word)≤100000; the total number of characters is not separately limited, so a valid total length can reach 10000000. The standard input/output is this site's wrapper.

输出格式

Output one line of n integers separated by spaces: the minimum number of replacements for each word, in input order.

样例 1

输入：

3
add
boook
break

输出：

1 1 0

样例 2

输入：

2
aa
abc

输出：

1 0

样例 3

输入：

1
zzzzzz

输出：

3