D-优美字符串_牛客小白月赛40

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$DD$ 给了 $dd$ 一个由小写英文字母组成的字符串，但是 $dd$ 觉得这个串太丑， $dd$ 觉得一个优美的字符串应该满足任意相邻字符都不相等，她想知道把给定字符串变成一个优美的字符串最少需要插入多少个字符，你只要告诉她，插入最少字符后的串的长度

第一行一个数T(1≤T≤10)
接下来T行，每行一个有且仅有小写英文字母构成的字符串s(1≤|s|≤100000)

输出T行，每行一个数，表示美化后串的最短长度

示例1

复制

4
a
ab
abbc
aaabb

复制

样例解释
第一个第二个不用动
第三个可以改成ababc
第四个可以改成abababab