Given a string s and a number k, find the maximum number of vowels in any substring of size k.

Vowels: ['a', 'e', 'i', 'o', 'u']

Example

String: "workaattech"
k: 3
Here, the substrings of size k and their vowel counts are:
wor => 1
ork => 1
rka => 1
kaa => 2
aat => 2
att => 1
tte => 1
tec => 1
ech => 1
Answer: 2

String: "substring"
k: 2
Here, the substrings of size k and their vowel counts are:
su => 1
ub => 1
bs => 0
st => 0
tr => 0
ri => 1
in => 1
ng => 0
Answer: 1

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.

For each test case, the input contains a string 's' and 'k' denoting the size of the substring.

Output format

For each test-cases, the output has n - k + 1 number denoting the elements of the resultant array.

Sample Input

2
workaattech 3
substring 2

Expected Output

2
1

Constraints

1 <= T <= 100

s consists of only lowercase English letters

1 <= s.length <= 104

1 <= k <= s.length