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 <= T <= 10), denoting the number of test cases.

Each test case contains a string S ( 1 <= length(S) <= 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

    Discussion

    Statistics


    71% Solution Ratio

    Ahasan_1999Earliest, 1M ago

    YouKnowWhoFastest, 0.0s

    steinumLightest, 1.2 MB

    steinumShortest, 618B

    Submit

    Login to submit