An Officer wants to give unique numbers to the newly recruit soldiers. He likes strange strings which can have only two digits '3' and '5'. The officer got a string S such that the character of the string is either '3' or '5' which can be called as strange digits or '!'. The officer wants and can replace '!' (exclamation mark) with one of the strange digits in the string to obtain a strange string. You have to tell the number of different ways with which he can do this so that the resulting strange string has no more than K different substrings. Help the Officer and find this number. Note : The Officer needs to replace all the exclamation marks.

Taking an example - Let us have a string 35!3! we can get 4 strange strings by replacing exclamation marks with the strange digits which are - 35333, 35335, 35533 and 35535 The corresponding numbers of different substrings are 11, 11, 12 and 11. For example, all different substrings of the string 35335 are 3, 5, 33, 35, 53, 335, 353, 533, 3533, 5335 and 35335. Here if K=11 then no. of ways will be 3. If K=12 then no. of ways will be 4. If K=10 then no. of ways will be 0.

Notes. Suppose S be some strange string. Then |S| denotes the length of the string S; S[i] (1 ≤ i ≤ |S|) denotes the ith character of S (the numeration of characters starts from 1); The string U of the length N is called a substring of S if for some k from 0 to |S| - N we have U[1] = S[k + 1], U[2] = S[k + 2], ..., U[N] = S[k + N].

Input

The first line of the input file contains a single positive integer T, the number of test cases. T test cases follow. The first line of each test case contains two space separated integers N and K. The second line contains the string S of the length N.

Output

For each test case, output a single line containing the answer for the corresponding test case. The output is the no. of strings of Length N made by replacing ! with 3 or 5 having maximum different substrings <=K.

Constraints

1 ≤ T ≤ 3535 1 ≤ N, K ≤ 50 For each string S from the input file we have that |S| = N and each character in S is either the strange digit (3 or 5) or the exclamation mark '!'.

NOTE What you have to do??

Download our code in which there are mistakes.

Link to download : Download our solution code

You have to add or edit the code to solve the problem.

So, its very simple, correct our given solution to solve the above writen problem and submit it here :)

NOTE : The code given by us is in JAVA but you can mold the code to C, C++, C# but please keep in mind that the logic code(the conditional statements,loops,etc.) should remain same.

If you come up with some other code that will be appreciable but will not be considered for giving prizes.