B – Ball Blasting Game

Morteza is playing a ball blasting game. In this game there is a chain of different colored balls. He is expected to explode as many balls as possible by aligning same-colored balls and making a sequence of them. To align balls, he can aim and shoot a new ball into a position in the chain, thus adding it there. If the new ball makes a sequence of two or more same-colored balls with its immediate neighbors, then the sequence blows up breaking the chain up into two parts. The two sections draw together to reform a single chain. Again, if the colors of the newly aligned balls (on joining ends of the two sections) match, the entire run of the suit explodes. New explosions ensue as long as joining sections bear new matches.

For instance, consider a chain symbolized in the string "GGGBWWRRWRR", with each letter representing the color of the corresponding ball in the chain. The train of balls therefore is composed of 6 sequences in 4 colors. Here, a ball can be added in 12 different positions. Shooting a red ball between the two middle red balls triggers two successive explosions which leave the chain "GGGBRR".

Morteza reaches a challenge stage in which he has only one ball to shoot but the color of which he can choose. He may not advance to the next stage unless he takes a shot that sets off the largest possible number of explosions. He has to replay all through this repetitive stage should he fail and needs your help in finding the largest possible number of successive explosions to save him a great deal of suffering.

Input

The first line of input contains an integer T≤100 denoting the number of test-cases. Each test-case is represented by a single line containing a string of upper case letters ('A'-'Z') of size of at most 100,000.

Output

For each test-case, output on a single line the maximum possible number of explosions.

Sample Input	Sample Output
3 GGGBWWRRWRR XAABCBAXAAAA CCC	2 4 1