Babur Biye

Babu is getting married. Babu's fiancé is a prominent programmer of Bangladesh. She told Babu to solve a problem. She won't say KOBUL until he solves the problem. The problem statement is given below.

A string containing English uppercase and lowercase characters. His ultimate goal is to make the given string beautiful.

A string is beautiful,

If it starts with some(possibly zero) English uppercase letters followed by some(possibly zero) English lowercase letters and further followed by some(possibly zero) English uppercase letters.

Or,

It starts with some(possibly zero) English lowercase letters followed by some(possibly zero) English uppercase letters and further followed by some(possibly zero) English lowercase letters.

For example: Wow, Alice, BoB, bABu, sobel, NICE strings are beautiful but HuHu, SmreenBErg, lEaN are not.

He may perform several operations on this string. In one operation, he can choose an index i and erase the i'th character of the string. He can perform this operation as many times as he wants.

Although Babu is a great programmer, he doesn't want to take risk of solving this problem alone. So, he asked his friend Sobel to help him to construct the longest beautiful string.

Input

The first line of the input contains an integer $T$ ($1 \le T \le 10$), denoting the number of test cases.

Each test case contains a string $S$ ($1 \le \texttt{Length of S} \le 10^5$).

Output

For each test case, print the length of the beautiful string.

Samples

5
Wow
BaBu
SoBeL
WOW
WorLD

3
3
4
3
5

2
UPPERlowerUPPER
lowerUPPERlower

15
15