So you must be familiar with Jake Harper from 'Two and a Half Men'. Once Alan gave him the job of painting a series of long, narrow canvases with bold colored stripes. As you know, Jake is very lazy kid, so he wants to minimise the number of brush strokes to paint the stripes on each canvas.

If the stripe pattern to be painted on a canvas is red-green-blue-green-red (RGBGR) then he would use three brush strokes to paint the pattern. In first stroke he would paint the entire canvas red, then he would paint band of green stripe in the middle and in the final stroke he would paint blue at the center of the green band.

So, in this problem you will be given pattern stripes as string like "RGBGR" and you have to calculate the number of strokes Jake will use to paint the pattern.

Input:
The first line contains a single number T, the number of test cases. T test cases follow. Each test case has a single line constaing a string of upper case characters 'A'-'Z', the pattern stripe.

Output:
Print a single line containing the minimum number of strokes needed to paint the pattern stripe.

Limits:
1<=T<=100
0<=L<=1000, L being the length of string

Sample Input:
4
RGBGR
RGRG
AABBCCDDCCBBAABBCCDD

Sample Output:
3
3
4
7

Problem Setter: Dhruva Bhaswar

Languages: Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 3 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0