Avinash Sir loves cakes very much so on his birthday his big brother Shubham sir decided to take him to cake shop to purchase the whole cake shop. Cakes were colored as Red and White and were arranged in sequential order.
Example : Red white Red White Red Red ... and so on
The Shopkeeper has a policy to sell cakes. A person can buy cakes if the color of the cakes form a palindromic subsequence.
Avinash Sir is very eager to eat all the cakes as soon as possible and want to buy all the cakes in minimum time.
Any Palindromic color subsequence of the cakes can be bought in 1 Sec. Help him to find the minimum time to buy all the cakes.
Input
The first line of the input contains an integer T, denoting the number of test cases. The next T lines contain a string S consisting of uppercase R and W where R denotes the red colored cakes and W denotes the white colored cakes.
Output
Print the minimum time to buy all cakes
Constraints
1 <= T <= 100
1 <= |S| <= 105 , length of the cake sequence
