#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define x first
#define y second
int a[10]={1,0,0,0,1,0,1,0,2,1};		
void solve(){
	int x,k;
	cin>>x>>k;
	string s=to_string(x);
	if(!k){
		cout<<x<<"\n";
	}else{
		while(k&&x!=1){
			int y=0;
			for(auto x:s){
				y+=a[x-'0'];
			}
			k--;
			x=y;
			s=to_string(x);
		}
		if(!k){
			cout<<x<<"\n";
		}else{
			if(k&1){
				
				cout<<"0\n";
			}else{
				cout<<"1\n";
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}