SOLVE
LATER
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
First test case:
\(freq[3] = 1\) and \(freq[4] = 2\). Since K=1, the minimum cost will be \((freq[3]+1) * (freq[4]+1) = 2 * 3 = 6\).