#include<iostream>
using namespace std;
int dig_ex[10]={1,0,0,0,1,0,1,0,2,1};//存储对照码 （0-9) 
int stor[100001][3];//测试用例范围 
int fun(int x){//函数功能实现 
	int sum=0,cache;
	while(x)
		{
			cache=x%10;
			sum+=dig_ex[cache];
			x/=10;
		}
		return sum;
}
int main(){
	int a,b,c,i,j,k,x;
	cin>>a;
	for(i=0;i<a;i++){
		cin>>stor[i][0]>>stor[i][1]; //i0是x,i1是k 
		}
	for(i=0;i<a;i++){
		for(j=0;j<stor[i][1];j++){
			stor[i][0]=fun(stor[i][0]);
			if(stor[i][0]==1||stor[i][0]==0){
				if((stor[i][1]-j)%2==0)
						{stor[i][0]=!stor[i][0];break;}
						else	break;
						}			
		} 
		} 
		for(i=0;i<a;i++)
		cout<<stor[i][0]<<'\n';
		return 0;
}