시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB235262213.333%

문제

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

입력

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$.

출력

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

예제 입력 1

2
8 1
45455151
2 1
42

예제 출력 1

9696
6