Rahul was travelling to Amritapuri in Coder Express to participate in Programming Contest. On his way he met a girl named Meenamma. Meenamma was beautiful and also very good in programming skills. She was busy in solving a problem.

Rahul find this an oppurtunity to help her and impress her. He asked her about the question. The question was you have been given a string and you have to count the number of capital letters in the string which are preceded by a lowercase letter. Can you help Rahul to impress her?

Input

First line contains an integer T that represents the number of test cases.Then follows the T lines each containing string of no more than 1000 characters The string contains letters only and no special characters.

Output

For each test case, print only one line, the output of your program.

Example

Input:
2
MeeNaLocHn
ArgaSundaRam

Output:
3
2