#pragma GCC optimize("Ofast")

//booster_^^
#include<bits/stdc++.h>

#define FC(a,b,c) for(int i=a;i<b;i++)cin>>c[i]
#define Fn(n) for(int i=0;i<n;i++)
#define fin(a,n) for(int i=0;i<n;i++)cin>>a[i]
#define F(a,b) for(int i=a;i<b;i++)
#define all(a) a.begin(),a.end()
#define umap_boost(x) x.reserve(1024);x.max_load_factor(0.25);

#define PII pair<int,int> 
#define ll long long
#define endl '\n'
using namespace std;

inline void cin_unlocked()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
}

template <typename T>
inline void stable_unique(vector<T>& v ){
    set<T> m(v.begin(),v.end());
    v.assign(m.begin(),m.end());
}


class dsu{
public:
    int n;
    vector<int> c;

    int q(int x){
        if(c[x]!=x){
            c[x]=q(c[x]);
        }
        return c[x];
    }
    void u(int a,int b){
        int fa=q(a);
        int fb=q(b);
        if(fa!=fb)
            c[fa]=fb;
    }

    dsu(int &_n){
        this->n=_n+5;
        this->c.resize(n);
        for(int i=0;i<n;i++)c[i]=i;
    }

};

int pow_mod(int a, int b,int mod) {//a^b
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = ans * a % mod; 
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int f[15]={1,0,0,0,1,0,1,0,2,1};

inline void solve(){
	int a,b;
	cin>>a>>b;
	if(!b){
		cout<<a<<endl;
		return;
	}

	while(b&&a>1){
		int c=0;
		while(a){
			c+=f[a%10];
			a/=10;
		}
		a=c;
		b--;
        // cout<<">>>"<<a<<' '<<b<<endl;
	}

    if(b)
	   a=a^(b%2);
	// cout<<b<<' '<<a<<endl;
    cout<<a<<endl;
}

int main(){
	cin_unlocked();
	int t;cin>>t;for(;t--;)
	   solve();

	return 0;
}