부분수 합

간단한 문제를 풀어 보자.

양의 정수가 주어졌을 때, 그 수에서 몇 개의 자릿수를 순서를 바꾸지 않고 이어 붙여 새로운 수를 만들 수 있다. 이렇게 만든 수를 원래 수의 부분수라고 하자. 예를 들어 $31415$에서 $3, 1, 1$을 택해 부분수 $311$을 만들 수 있다.

$N$자리 양의 정수가 주어진다. $K$개의 자릿수를 골라 한 부분수를 만들고 남은 $N-K$개의 자릿수로 다른 부분수를 만들 수 있다. 골라야 하는 자릿수 $K$가 주어질 때, 두 부분수의 합의 최댓값을 구하자. 부분수가 앞에 0을 포함해도 된다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다 $(1 \leq T \leq 10,000)$.

각 테스트 케이스의 첫째 줄에 두 정수 $N, K$ $(2 \leq N \leq 18, 1 \leq K < N)$가 주어지고, 둘째 줄에 $N$자리 양의 정수가 주어진다. 입력으로 주어지는 수는 앞에 0이 없지만, 그 부분수는 앞에 0이 있을 수 있다.

각 테스트 케이스마다 조건을 만족하는 두 부분수의 합의 최댓값을 한 줄에 출력한다.