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

vector<int>f = {1,0,0,0,1,0,1,0,2,1};
#define ll long long
ll calc(ll n, ll m){
	if(m == 0)return n;
	if(n == 0 || n == 1)m %= 2;
	if(m == 0)return n;
	ll sum = 0;
	if(n == 0)return calc(1, m - 1);
	while(n){
		int base = n % 10;
		sum += f[base];
		n /= 10;
	}
	return calc(sum, m - 1);
}

int main(){
	int T;
	scanf("%d", &T);
	while(T --){
		int n, m;
		scanf("%d%d",&n,&m);
		printf("%lld\n", calc(n, m));
	}
}