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

#define forn(i,a,b) for(int i = a; i < (b); i++)
#define fore(i,a,b) for(int i = a; i <= (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using ld = long double;
using ii = pair<int, int>;

const int a[] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};

ll f(ll x)
{
    ll sum=0;
    while(x)
    {
        sum += a[x % 10];
        x /= 10;
    }
    return sum;
}

void solve()
{
    ll x,K; cin>>x>>K;
    while(K--)
    {
        x = f(x);
        if (x <= 1)
        {
            cout << (x ^ (K % 2)) << '\n';
            return;
        }
    }
    cout << x << '\n';
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    int t; cin>>t;
    forn(i,0,t) solve();
}