You are given with a string and a number K.

You need to find the count of substrings of length K in given string which are special palindromes.

Now, what is a special palindrome?

• Ofcourse, a palindrome ! (string that reads the same backwards as forwards)
• Contains only single distinct character.
• The mirror image and original image of the single distinct character is same.

So,

ABA is a palindrome but not a special palindrome ( 2 distinct characters !)

CCC is a palindrome with single distinct character but not a special palindrome (C's mirror image doesn't match with original image)

AAA is.. yes! A SPECIAL PALINDROME with length 3.

Input Format:

First line - T denoting number of testcases

For each testcase

Single line containing input string and K with space in between.

Output Format:

For each testcase

print the count of special palindromes with length K in new line.

Constraints:

1<=T<=1000000

1<=length(input string)<=1000000

1<=K<=length(input string)

input string contains only uppercase letters