자음

영어에는 모음 또는 자음인 26개의 글자가 있다. 이 문제에서는 a, e, i, o, u를 모음으로, 나머지 21개의 글자를 자음으로 간주한다.

Greatest Colorful Jungle에 사는 한 부족에는 영어 글자를 사용해 구성원의 이름을 짓는 전통이 있다. 하지만 이름은 부족 내에서 그 구성원의 사회적 지위를 나타내므로, 새 구성원에게 좋은 이름을 지어 주기는 쉽지 않다. 부여받은 이름이 드물수록 그 사람의 사회적 특권이 더 크다고 여겨진다.

부족의 지도자는 전문 언어학자이다. 그는 발음하기 어려운 이름이 드물며, 그 이유가 그러한 이름에 연속된 자음이 너무 많기 때문이라는 사실을 알아차린다. 따라서 그는 부족 구성원의 사회적 지위가 그 이름의 n-값으로 결정된다고 선언한다. n-값은 이름에서 적어도 n개의 연속된 자음을 포함하는 부분 문자열의 개수이다. 예를 들어 n = 3일 때, 이름 "quartz"의 n-값은 4이다. 부분 문자열 쿼츠, 우아츠, 아츠, 르츠가 각각 적어도 3개의 연속된 자음을 포함하기 때문이다. n-값이 클수록 부족 내에서의 사회적 지위가 더 높다. 두 부분 문자열은 시작점이나 끝점이 다르면 서로 다른 것으로 간주한다. 이는 같은 글자로 이루어진 경우에도 마찬가지이다. 예를 들어 "tsetse"에는 연속된 자음 두 개를 포함하는 부분 문자열이 11개 있으며, 그중 일부는 "tsetse"와 "tsetse"처럼 같은 글자를 포함한다.

부족의 모든 구성원은 지도자로부터 이름과 n을 부여받아야 한다. 지도자는 언어학자이므로 주어진 이름이 의미 있도록 할 수 있지만, n-값을 계산하는 데는 능숙하지 않다. 지도자가 각 이름의 n-값을 구할 수 있도록 도와주자. 서로 다른 이름에는 서로 다른 n 값이 연관될 수 있음에 유의한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 0 < n ≤ L.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ L ≤ 100.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ L ≤ $10^{6}$. 입력 파일의 크기는 6MB 이하이다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 길이가 L인 문자열로 구성원의 이름과 정수 n이 주어진다. 각 이름은 하나 이상의 영어 소문자로 이루어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 구성원 이름의 n-값이다.