# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Babur Biye

By error26 · Limits 1s, 512 MB

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

InputOutput
5
Wow
BaBu
SoBeL
WOW
WorLD

3
3
4
3
5

InputOutput
2
UPPERlowerUPPER
lowerUPPERlower

15
15


### Statistics

76% Solution Ratio

Ahasan_1999Earliest, Dec '20

rahat_chyFastest, 0.0s

steinumLightest, 1.2 MB

steinumShortest, 618B