F. Sum of Numbers
time limit per test
1 second
memory limit per test
1024 mebibytes
input
standard input
output
standard output

Given $$$n$$$ digits from '1' to '9', you can add $$$k$$$ '+' to turn it into an expression. Find the minimum value of the expression.

Input

There are multiple test cases.

The first line of the input contains one integer $$$T$$$ ($$$1\le T\le 2\cdot 10^4$$$) — the number of test cases.

For each test case:

The first line contains two integers $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) and $$$k$$$ ($$$1\le k\le 6$$$, $$$k<n$$$) — the number of digits and the number of '+'.

The second line contains a string of length $$$n$$$, which consists of digits from '1' to '9'.

The sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output the answer in one line.

Example
Input
2
8 1
45455151
2 1
42
Output
9696
6