说明

给定一个字符串 s ，定义 s 为Even String 需要满足两个条件 : 

1. 字符串 s 的长度为偶数
2. 字符串 s 奇数位置的字符和下一个位置的字符相同

例如, 空字符串 ， "oooo" , "aa" , "ppqq"都是Even String
现在你可以任意删除某个位置的字符，那么要将 s 改变为 Even String ， 至少需要删除多少次。

输入格式

一个正整数T ， 代表数据的组数。
下面T行，分别代表T组数据。
每行一个字符串 |s| <= 200000

输出格式

输出包含T行正整数，代表最少的删除次数。

样例

6
aabbdabdccc
zyx
aaababbb
aabbcc
oaoaaaoo
bmefbmuyw

3
3
2
0
2
7