자음 (Large)

영어 알파벳 26글자는 모음과 자음으로 나뉜다. 이 문제에서는 a, e, i, o, u를 모음으로 보고 나머지 21글자를 자음으로 본다.

Greatest Colorful Jungle에 사는 한 부족은 영어 알파벳으로 구성원의 이름을 짓는다. 이름이 부족 안에서 그 구성원의 지위를 결정하기 때문에 좋은 이름을 짓기가 쉽지 않다. 흔하지 않은 이름일수록 지위가 높다고 여긴다.

부족장의 직업은 언어학자다. 부족장은 흔하지 않은 이름이 발음하기 어렵고, 그 까닭이 자음이 너무 여러 개 연달아 이어지기 때문임을 알아냈다. 그래서 구성원의 지위를 이름의 $n$-값으로 정한다고 선언했다. $n$-값은 자음이 $n$개 이상 연속으로 들어 있는 부분 문자열의 개수다. $n = 3$일 때 이름 quartz의 $n$-값은 4다. 부분 문자열 quartz, uartz, artz, rtz가 각각 자음 3개 이상을 연속으로 포함하기 때문이다. $n$-값이 클수록 지위가 높다. 시작 위치나 끝 위치가 다르면 글자 구성이 같아도 서로 다른 부분 문자열로 센다. 이름 tsetse에는 자음이 2개 연속으로 들어 있는 부분 문자열이 11개 있는데, 그중 앞의 세 글자로 이루어진 것과 뒤의 세 글자로 이루어진 것은 둘 다 tse지만 따로 센다.

부족장이 구성원마다 이름과 $n$을 정해 준다. 부족장은 뜻이 통하는 이름을 짓는 데는 문제가 없지만 $n$-값을 계산하는 데는 서툴다. 이름마다 $n$-값을 구하라. 이름에 따라 $n$이 다를 수 있다.

첫째 줄에 테스트 케이스 개수 $T$가 주어진다. 다음 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 영어 소문자 $L$개로 이루어진 이름과 정수 $n$이 공백 하나를 사이에 두고 주어진다.

제한

• $1 \le T \le 100$
• $1 \le L \le 10^6$
• $0 < n \le L$
• 입력 전체 크기는 6 MB 이하다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 그 구성원 이름의 $n$-값이다.