Consonants (Large)

The English alphabet has 26 letters, and each of them is either a vowel or a consonant. In this problem a, e, i, o and u are vowels, and the other 21 letters are consonants.

A tribe living in the Greatest Colorful Jungle names its members with English letters. Picking a good name is not easy, because the name fixes the member's standing inside the tribe. The less common the name, the higher the standing.

The leader of the tribe works as a linguist. He noticed that uncommon names are hard to pronounce, and that they are hard to pronounce because they contain too many consecutive consonants. So he declared that a member's standing is given by the $n$-value of the name, which is the number of substrings that contain at least $n$ consecutive consonants. For $n = 3$ the name quartz has $n$-value 4, because the substrings quartz, uartz, artz and rtz each contain at least 3 consecutive consonants. A larger $n$-value means a higher standing. Two substrings count as different when they start or end at different positions, even when they spell the same letters. The name tsetse contains 11 substrings with 2 consecutive consonants, and among them the substring formed by the first three letters and the substring formed by the last three letters both spell tse, yet they are counted separately.

The leader assigns a name and a value of $n$ to every member. He has no trouble making the names meaningful, but he is bad at computing $n$-values. Compute the $n$-value of each name. Different names may come with different values of $n$.

The first line contains the number of test cases $T$. Each of the next $T$ lines describes one test case: the name of a member, given as a string of $L$ lowercase English letters, then a space, then an integer $n$.

Limits

• $1 \le T \le 100$
• $1 \le L \le 10^6$
• $0 < n \le L$
• The whole input is at most 6 MB.

For each test case, print one line in the form Case #x: y, where x is the test case number starting from 1 and y is the $n$-value of that member's name.