Given a large string of integers S of length N, divide the string into K non-empty substrings such that the sum of cost of each substring is minimised. The cost of a substring is \(\prod_{i = 0}^{9} (freq[i] + 1)\), where \(freq[i]\) denotes the number of occurrence of integer i in the substring under consideration.

Input
First line contains a single integer T denoting the number of test cases.
First line of each test case contains two integers N and K.
Second line of each test case contains the string S

Output
For each test case output the minimum cost.

Constraints
1 <= T <= 50
1 <= N <= 500

1 <= K <= N

0 <= S[i] <= 9