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

#define endl '\n'
#define int long long

void solve() {
    vector<int> mp(10);
    mp[0] = 1, mp[1] = 0, mp[2] = 0, mp[3] = 0, mp[4] = 1;
    mp[5] = 0, mp[6] = 1, mp[7] = 0, mp[8] = 2, mp[9] = 1;
    int x, k;
    cin >> x >> k;
    if(!k) {
        cout << x << endl;
        return;
    }
    for(int i = 1;i <= k;i++) {
        if(x <= 1) {
            int num = k - i + 1;
            if(num & 1) cout << (x ^ 1) << endl;
            else cout << x << endl;
            return;
        }
        int tmp = 0;
        while(x) {
            tmp += mp[x % 10];
            x /= 10;
        }
        x = tmp;
    }
    cout << x << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}