#include <cstdio>
#include <cstring>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int val[10]={1,0,0,0,1,0,1,0,2,1};
int f(int x){
	int res=0;
	do res+=val[x%10],x/=10;while(x);
	return res;
}
int pos[1003];
int arr[1003];
int main(){
	int tc=read();
	memset(pos,-1,sizeof pos);
	while(tc--){
		int x=read(),k=read();
		if(!k){printf("%d\n",x);continue;}
		--k;x=f(x);
		if(!k){printf("%d\n",x);continue;}
		arr[pos[x]=0]=x;
		bool fl=1;
		for(int i=1;i<=k;++i){
			x=f(x);
			if(~pos[x]){
				printf("%d\n",arr[pos[x]+(k-i)%(i-pos[x])]);
				for(int j=0;j<i;++j) pos[arr[j]]=-1;
				fl=0;
				break;
			}
			arr[pos[x]=i]=x;
		}
		if(fl){
			for(int i=0;i<=k;++i) pos[arr[i]]=-1;
			printf("%d\n",arr[k]);
		}
	}
	return 0;
}