#include<bits/stdc++.h>
#define LL long long
#define mk make_pair
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int f[10] = {1,0,0,0,1,0,1,0,2,1};
inline int read(){
	int v = 0,c = 1;char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') c = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		v = v * 10 + ch - 48;
		ch = getchar();
	}
	return v * c;
}
inline int getf(int n){
	int sum = 0;
	int now = n;
	while(now){
		sum += f[now % 10];
		now /= 10;	
	}
//	printf("%d %d\n",n,sum);
	return sum;
}
inline int work(int n,int k){
	if(!k) return n;
	if(n == 1) return !(k & 1);
	if(n == 0) return k & 1;
	return work(getf(n),k - 1);
}
int main(){
	int T = read();
	while(T--){
		int n = read(),k = read();
		printf("%d\n",work(n,k));	
	}
    return 0;
}