Problem F: Beautiful pairs

Problem F: Beautiful pairs

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 618  Solved: 124
[Submit][Status][Web Board]


A pair of English letters (a, b) is considered beautiful iff one of them is uppercase, the other is lowercase and both of them are consonants. (English letters except a, e, i, o, u, w and y). Now give you a string which is consists of lowercase English letters. Now you can change several letters from lowercase to uppercase. Please write a program to calculate the maximum number of beautiful pairs formed by adjacent letters. 

Note: If you change x to X, then all x in the string will become X.

For example, if we have string strength, we can change it to StRenGtH. In this case, (S,t), (t,R),(n,G),(G,t) and (t,H) are beautiful. So the result is 5.


The first line of input is the number of test cases T (1 <= T <= 10)

For each test case, there will be a string consists of lowercase English letters. The length of the string does not exists 10000.


For each test case, print the maximum number of adjacent beautiful pairs you can find.

Sample Input


Sample Output