#include <bits/stdc++.h>
#define N (200000 + 10)  /*------------------ #define ------------------*/
#define M (400000 + 10)
#define MOD (1000000000 + 7)
//#define MOD (998244353)
#define INF (0x3f3f3f3f)
#define LNF (3e18)
#define mod(a,b) (((a)%(b)+(b))%(b))
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<double,double> PDD;

LL a[10] = {1,0,0,0,1,0,1,0,2,1};

auto solve(){
	
	LL n,k;
	cin >> n >> k;
	
	if(!k){
		cout << n << '\n';
		return;
	}
	
	auto f = [&](LL x){
		int ans = 0;
		while(x){
			ans += a[x % 10];
			x /= 10;
		}
		return ans;
	};
	
	LL t = 0,now = n;
	while(now != 0 && t < k){
		now = f(now);
		t ++ ;
	}
	
	if(t == k){
		cout << now << '\n';
	}else{
		cout << ((k - t + 1) % 2 == 1 ? 0 : 1) << '\n';
	}
}

signed main(){
	IOS
	int T = 1;
	//
	cin >> T;
	while(T -- ) solve();
	//while(T -- ) cout << (solve() ? "YES" : "NO") << '\n';

    return 0;
}