minimalOperations (Adjacent Duplicate Replacements)

For each word, find the minimum number of character replacements so that no two adjacent characters are the same.

输入格式

The first line contains n (1≤n≤100); each of the next n lines is a lowercase word of length 2..100000.

输出格式

For each word, output one line with the minimum number of replacements.

样例 1

输入：

3
add
boook
break

输出：

1
1
0

样例说明

A linear-scan/dynamic-programming solution follows directly from the rules; the examples have been checked one by one against an independently built oracle.