Description

咕咕有一串漂亮的珠串，珠串上有 \(n\) 个珠子相邻排列（首尾不相接），且颜色均为红绿蓝三色之一。

咕咕可以不断地执行一种操作：将珠串上颜色不同的两个相邻珠子 \(A\) 和 \(B\) 合并为一个珠子，合并出的珠子的颜色为与 \(A\) 和 \(B\) 均不同的第三种颜色，且仍然是红绿蓝三色之一。例如，当我们将红色与绿色的珠子合并，将得到蓝色的珠子。

现在给定初始珠串的珠子的颜色排列，咕咕想知道他最多可以让初始珠串的长度变为多短。

Format

Input

共有 \(t\) 组输入数据，第一行为一个整数 \(t\) 表示数组组数（\(1\leq t \leq 10^3\)）。

每组数据共一行，第一行为一个字符串 \(s\)，代表了给定的珠串，字符串 \(s\) 的长度 \(n\) 即为珠串上珠子的数量（\(1\leq n \leq 10^3\)）。

字符串 \(s\) 包含且仅包含小写字母 r, g, b，分别代表了红色，绿色与蓝色。

Output

每组数据输出共一行，第一行为一个整数 \(m\)，表示珠串的最短长度。

Sample 1

Input

5
rr
rgbb
rbgb
rrgg
rrggbb

Output

2
1
1
2
2