#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < ll >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 1e6 + 10;
constexpr ll B = 1e16;

int n, K;
string num;

vec tnum;
const bool operator < (const vec &x, const vec &y) {
	//cerr << "!COMP: " << x << " " << y << endl;
	if(x.size() != y.size()) return x.size() < y.size();
	per(i, (int)x.size() - 1, 0)
		if(x[i] != y[i]) return x[i] < y[i];
	return 1;
}

ll pw[20];

void compose(vec &x) { // zhengxu 1212120
	vec ret;  reverse(x.begin(), x.end()); // 0121221
	rep(i, 0, (int)x.size() - 1) {
		if(i % 16) ret.back() = x[i] * pw[i % 16] + ret.back();
		else ret.eb(x[i]);
	} x = ret;
}

void depose(vec &x) { // 01212121
	//reverse(x.begin(), x.end());
	vec ret;
	rep(i, 0, (int)x.size() - 1) {
		rep(j, 0, 15) ret.eb( x[i] % 10 ), x[i] /= 10;
	} while(ret.size() && ret.back() == 0) ret.pop_back(); x = ret;
}

vec getp(int l, int r) {
	vec ret; l--, r--;
	rep(i, l, r) ret.eb(tnum[i]);
	compose(ret);
	//cout << l << " " << r << " " << ret[0] << endl;
	return ret;
}

vec operator * (const vec &a, const vec &b) {
	vec t(max(a.size(), b.size()) + 1, 0);
	rep(i, 0, max(a.size(), b.size())) {
		if(i < a.size()) t[i] += a[i];
		if(i < b.size()) t[i] += b[i];
		if(t[i] >= B) t[i + 1] += t[i] / B, t[i] %= B;
	} while(t.back() == 0) t.pop_back(); 
	/*cerr << "CALC: " << a << " " << b << " " << t << endl;*/ return t;
}

vec get(const vec &pot) {
	int cur = 1; vec ret;
	//for(auto v : pot) cerr << v << " "; cerr << endl;
	for(auto v : pot) {
		int l = cur, r = l + v - 1;
		//cerr << l << " " << r << " " << getp(l, r) << endl;
		ret = ret * getp(l, r);
		cur += v;
	} //cerr << "!" << ret << endl;
	return ret;
}

void solve() {
	cin >> n >> K >> num;
	//reverse(num.begin(), num.end());
	vec().swap(tnum);
	for(auto &v : num) v -= '0', tnum.eb(v);
	int len = n / (K + 1);
	vec ans; bool fl = 0;
	auto upd = [&](const vec &ret) {
		if(!fl) ans = ret, fl = 1;
		else chkmin(ans, ret);
	};
	auto runit = [&](int chk) {
		int t = 1; rep(i, 1, K + 1) t = t * 3;
		auto calc = [&](int x) {
			int ret = 0; rep(j, 0, K) ret += x % 3 - 1, x /= 3;
			return ret;
		};
		rep(s, 0, t - 1) if(calc(s) + len * (K + 1) == n) {
			vec pot(K + 1, len); int x = s;
			rep(j, 0, K) pot[j] += x % 3 - 1, x /= 3;
			int tfl = 0;
			rep(j, 0, K) if(pot[j] <= 0) tfl = 1;
			if(tfl) continue;
			rep(j, 0, K) tfl |= pot[j] == len + 1;
			if(!tfl) continue;
			if(!fl) fl = 1, ans = get(pot);
			else chkmin(ans, get(pot));
		}
	};
	runit(0); len++; runit(1); depose(ans);
	//cerr << ct << endl;
	reverse(ans.begin(), ans.end());
	for(auto v : ans) cout << v; cout << endl;
}

int main() {
#ifdef YJR_2333_TEST
	freopen("1.in", "r", stdin);
#endif
	pw[0] = 1; rep(i, 1, 18) pw[i] = pw[i - 1] * 10;
	ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T; cin >> T;
	for(; T; T--) solve(); return 0;
}