#include<bits/stdc++.h>
#include<bits/extc++.h>

using namespace std;
int dp[42][22][2];
int dp1[42][22][2];

void printNum(int i, int j, int k, string &x, bool &st) {
    if (i) {
        int nx = dp[i][j][k];
        int val = k ? 10 - (nx&1) - (x[i] - '0') : 0;
        if (val) st = true;
        if (st) {
            cout << val;
        }
        printNum(i-1, nx/2, nx&1, x, st);
    }
}
main() {
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t --) {
        int ansI, ansJ, ansK, ansR = 100000;
        string x;
        int k;
        cin >> x >> k;
        reverse(x.begin(), x.end());
        if (k == 0) {
            cout << 1;
            for (int i = 0; i < x.size(); i ++) {
                if (x[i] != '9') break;
                cout << 0;
            }
        cout << endl;
            continue;
        }
        x = " " + x;
        while (x.size() < 40) {
            x += '0';
        }
        memset(dp, ~0, sizeof dp);
        dp[0][0][0] = 0;
        dp1[0][0][0] = 0;
        for (int i = 1; i < x.size(); i ++) {
            for (int j = 0; j <= k; j ++) {
                dp1[i][j][0] = 10000;
                dp1[i][j][1] = 10000;
                if (dp[i-1][j][0] != -1) {
                    dp[i][j][0] = 2 * j;
                    dp1[i][j][0] = dp1[i-1][j][0];
                }
                if (dp[i-1][j][1] != -1 && x[i] != '9' && dp1[i][j][0] > dp1[i-1][j][1]) {
                    dp[i][j][0] = 2 * j + 1;
                    dp1[i][j][0] = dp1[i-1][j][1];
                }
                if (j && dp[i-1][j-1][0] != -1 && x[i] != '0') {
                    dp[i][j][1] = 2 * (j-1);
                    dp1[i][j][1] = i;
                }
                int r = (x[i] == '9' ? dp1[i-1][j-1][1] : i);
                if (j && dp[i-1][j-1][1] != -1 && dp1[i][j][1] > r) {
                    dp[i][j][1] = 2 * (j-1) + 1;
                    dp1[i][j][1] = r;
                }
                //cout << i << " " << j << " " << dp[i][j][0] << " " << dp[i][j][1] << endl;
            }
            if (dp[i][k][0] != -1 && ansR > dp1[i][k][0]) {
                bool nuli = false;
                printNum(i, k, 0, x, nuli);
                if (!nuli) {
                    cout << 1;
                }
                cout << endl;
                break;
            }
        }

    }
}
/*


*/