Rahul is a young chap who loves strings but simply hates mathematics. While his friend Ramesh is in love with mathematics but hates strings. So their teacher decided to take a test which combined both these topics so that neither of them gets a better hand over the other.

Their teacher gave both of them a single string. The string consists of digits from 0-9 only. Then their teacher asked them to divide the string into exactly K parts such that each part is not greater than a fixed value Z. Since there could be many such ways to divide the string their teacher asked them to divide in such a manner that maximized the final sum of all the K parts.

This question really baffled both of them. Since they are in trouble they ask your help in finding out the maximum sum.

If it is not possible to cut the string into K parts satisfying the given conditions print -1.

Input:

The first line contains T denoting the number of test cases. The first line of each test case contains 2 space separated integers K and Z that are the number of parts in which the string is to be cut and the value that each part should not exceed. The second line of each test case contains the string.

Output:

For each test case print the required answer.

Constraints:

1<= T <=10

1<= K <=100

1 <= Z <=10^9

1<= length of string <= 100
The string contains characters from [0-9] only