No Pairs Allowed

You are given n words of lowercase English letters. In each word, any character may be replaced with any lowercase English letter. Find the minimum number of replacements so that the final string has no two equal adjacent characters.

输入格式

The first line contains n (1≤n≤100), followed by n lines each with one word; 2≤length of each word≤100000, and all characters are a–z.

输出格式

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

样例 1

输入：

3
add
boook
break

输出：

1 1 0

样例 2

输入：

2
aa
aaa

输出：

1 1

样例 3

输入：

2
ab
zzzz

输出：

0 2