Cho ~1~ xâu ~s~ có độ dài ~n~ và chỉ gồm các chữ số từ '1' đến '9'.

Yêu cầu: Hãy thêm ~k~ dấu cộng chèn vào giữa các chữ số trên sao cho:

• Xâu được tạo ra là một biểu thức hợp lệ. Ví dụ: "2 + 3 + 5" là biểu thức hợp lệ, nhưng +1, 1 + +2, 10+ thì không.

• Kết quả tạo ra sau khi thêm ~k~ dấu cộng là nhỏ nhất có thể.

Input

• Dòng ~1~: Gồm số nguyên ~T~ là số lượng test cases.

• Với mỗi test case:

  • Dòng thứ nhất: Gồm ~2~ số ~n~ ~(2 \le n \le 2 \times 10^5)~ và ~k~ ~(1 \le k \le 6, k < n)~ là độ dài xâu ~s~ và số lượng dấu cộng phải chèn.

  • Dòng thứ hai: Gồm xâu ~s~ có độ dài ~n~ và chỉ gồm các ký tự từ '1' đến '9'.

Dữ liệu đảm bảo tổng ~n~ trong tất cả các test cases không vượt quá ~2 \times 10^5~.

Output

Với mỗi test case, in ra kết quả trên một dòng.

Scoring

Sample Input 1

3
8 1
12341235
3 1
911
7 6
1234567

Sample Output 1

2469
20
28

Notes

• Test case ~1~: Biểu thức tối ưu là ~1234 + 1235 = 2469~.

• Test case ~2~: Biểu thức tối ưu là ~9 + 11 = 20~.

• Test case ~3~: Biểu thức tối ưu là ~1 + 2 + 3 + 4 + 5 + 6 + 7 = 28~.