#include <bits/stdc++.h>

using namespace std;

#define int long long
#define REP(i, n) for (int i = 0; i < (n); i++)
typedef vector<int> vi;
typedef vector<vi> vvi;
vi mp = {1,0,0,0,1,0,1,0,2,1};

int getnext(int v) {
    int tot =0;
    for (auto c: to_string(v)) {
        tot += mp[c - '0'];
    }
    return tot;
}
int solve() {
    int x,k;cin>>x>>k;
    map<int,int> seen;
    vi carr;
    int cur = x;
    int curtime = 0;
    while (true) {
        if (curtime == k) {
            return cur;
        }
        if (seen.find(cur) != seen.end()) {
            int idx = seen[cur];
            int diff = curtime - idx;
            int rem = (k - idx)%diff;
            return  carr[idx + rem];
        } else {
            seen[cur] = curtime;
            carr.push_back(cur);
            curtime++;
            cur = getnext(cur);
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;cin>>tc;


    REP(i, tc) {
        cout<<solve()<<"\n";
    }


}