Background

good luck!

Description

ICPC比赛场地会有很多不同颜色的气球，现在有这么$n$个人，站成一排，每人手上都拿着一个气球，颜色是R，G，B当中的一种，但是，猫猫头为了不让相邻的两人手上的气球颜色相同，就要给他们更换手上气球的颜色，那么，最少更换多少个气球呢？

Format

Input

输入的第一行是一个整数$t$，表示接下来有$t$行，每行都是一个由大写RGB组成的字符串，每一行表示一组输入。

所有字符串的长度总和不超过 $10^6$

Output

输出一共$t$行，每行一个整数表示最少更换的气球数。

Samples

3
RGBRGB
RRGGBB
RRR

0
3
1

Limitation

1s, 1024KiB for each test case.