#include <iostream>

using namespace std;

void solve() {
    int n, d;
    cin >> n >> d;
    string s;
    cin >> s;
    for (int i = 0; i < n; ++i) {
        if (s[i] - '0' >= d) {
            cout << s[i];
        } else {
            cout << d;
            for (int j = i; j < n; ++j) {
                cout << s[j];
            }
            cout << '\n';
            return;
        }
    }
    cout << d << '\n';
}

int main() {
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        solve();
    }
    return 0;
}

def layer(n, x, y):
    return min([x, y, n + 1 - x, n + 1 - y])


def solve():
    n, x1, y1, x2, y2 = map(int, input().split())
    print(abs(layer(n, x1, y1) - layer(n, x2, y2)))


t = int(input())
for _ in range(t):
    solve()

#include "bits/stdc++.h"
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int>b(n-1), a;
    for(int i = 0; i < n - 1; i++) cin >> b[i];
    a.emplace_back(b[0]);
    for(int i = 0; i < n - 2; i++){
        a.emplace_back(min(b[i], b[i + 1]));
    }
    a.emplace_back(b[n - 2]);
    for(auto &i : a) cout << i << ' ';
    cout << "\n";
}
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50;

int fib[MAXN];

void build() {
	fib[0] = fib[1] = 1;
	for (int i = 2; i < MAXN; ++i)
		fib[i] = fib[i - 2] + fib[i - 1];
}

bool solve(int n, int x, int y) {
	if (n == 1) return true;
	if (fib[n - 1] <= y && y < fib[n])
		return false;
	if (fib[n] <= y)
		y -= fib[n];
	return solve(n - 1, y, x);
}

int main() {
	int t; cin >> t;
	build();
	while (t--) {
		int n, x, y; cin >> n >> x >> y;
		cout << (solve(n, --x, --y) ? "YES" : "NO") << '\n';
	}
}

#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int32_t num_tests;
    std::cin >> num_tests;

    for(int32_t t = 0; t < num_tests; t++) {
        int64_t k;
        std::cin >> k;

        std::vector<int32_t> digits;
        while(k > 0) {
            digits.push_back(k % 9);
            k /= 9;
        }
        std::reverse(digits.begin(), digits.end());

        for(int32_t i = 0; i < digits.size(); i++)
            std::cout << (char)(digits[i] < 4 ? (digits[i] + '0') : (digits[i] + '1'));
        std::cout << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int sz(int v, vector<vector<int>> &g, vector<bool> &used){
    used[v] = true;
    int s = 1;
    for(int u: g[v]){
        if(!used[u]) s += sz(u, g, used);
    }
    return s;
}

void remove(vector<int> &from, int x){
    for(int &e: from){
        if(e == x){
            swap(e, from.back());
            from.pop_back();
            return;
        }
    }
}

void solve(int tc) {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> sl(n);
    for(int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        sl[--u].emplace_back(--v);
        sl[v].emplace_back(u);
    }
    int k = sqrt(n);
    if(n != k * k || m != n + k){
        cout << "NO";
        return;
    }
    for(int i = 0; i < n; ++i){
        if(sl[i].size() != 2 && sl[i].size() != 4){
            cout << "NO";
            return;
        }
    }
    vector<bool> used(n);
    if(sz(0, sl, used) != n){
        cout << "NO";
        return;
    }
    for(int i = 0; i < n; ++i){
        if(sl[i].size() == 2) continue;
        for(int j = 0; j < sl[i].size();){
            int u = sl[i][j];
            if(sl[u].size() > 2){
                remove(sl[i], u);
                remove(sl[u], i);
            }
            else{
                j++;
            }
        }
    }
    used = vector<bool>(n);
    for(int i = 0; i < n; ++i){
        if(!used[i] && sz(i, sl, used) != k){
            cout << "NO";
            return;
        }
    }
    cout << "YES";
}

bool multi = true;

signed main() {
    cout.tie(nullptr);
    int t = 1;
    if (multi)cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
        cout << "\n";
    }
    return 0;
}

M = 10 ** 9 + 7


def pw(a, n):
    if n == 0:
        return 1
    b = pw(a, n // 2)
    return b * b % M * (a if n % 2 == 1 else 1) % M


def obr(x):
    return pw(x, M - 2)


def cnk(n, k):
    return fact[n] * obr(fact[k]) % M * obr(fact[n - k]) % M


def solve():
    n, k = map(int, input().split())
    c = [-1] + [int(x) for x in input().split()]
    if k == 1:
        print(1)
        return
    dp = [[0] * (n // k + 1) for i in range(n + 1)]  # dp[i][j] = number for i prefix with j blocks
    dp[0][0] = 1
    for i in range(1, n + 1):
        for j in range(0, n // k + 1):
            if j > 0:
                sz = 1
                for s in range(i - 1, - 1, -1):
                    if c[s] == c[i]:
                        sz += 1
                        if sz >= k:
                            dp[i][j] += dp[s - 1][j - 1] * cnk(sz - 2, k - 2) % M
                            dp[i][j] %= M
            dp[i][j] += dp[i - 1][j]
            dp[i][j] %= M
    for j in range(n // k, -1, -1):
        if dp[n][j] > 0:
            print(dp[n][j])
            return


t = int(input())
fact = [1] * 101
for i in range(1, 101):
    fact[i] = fact[i - 1] * i % M
for _ in range(t):
    solve()

from sys import stdin
input = lambda: stdin.readline().strip()


M = 10 ** 9 + 7
cnk = [[0] * (5000 + 1) for i in range(5000 + 1)]


def solve():
    n, k = map(int, input().split())
    c = [-1] + [int(x) for x in input().split()]
    if k == 1:
        print(1)
        return
    dp = [[0, 0] for i in range(n + 1)]  # dp[i] = [number, max] for i prefix
    dp[0][0] = 1
    for i in range(1, n + 1):
        sz = 1
        for s in range(i - 1, - 1, -1):
            if c[s] == c[i]:
                sz += 1
                if sz == k:
                    dp[i][1] = dp[s - 1][1] + 1
                if sz >= k:
                    if dp[s - 1][1] < dp[i][1] - 1:
                        break
                    dp[i][0] += dp[s - 1][0] * cnk[sz - 2][k - 2] % M
                    dp[i][0] %= M
        if dp[i][1] < dp[i - 1][1]:
            dp[i] = [0, dp[i - 1][1]]
        if dp[i][1] == dp[i - 1][1]:
            dp[i][0] += dp[i - 1][0]
            dp[i][0] %= M
    print(dp[n][0])


for i in range(5000 + 1):
    cnk[i][0] = 1
for i in range(1, 5000 + 1):
    for j in range(1, i + 1):
        cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % M

t = int(input())
for _ in range(t):
    solve()