#include<bits/stdc++.h>
using namespace std;
bool is_prime(int x){
	for(int i = 2;i*i<=x;i++){
		if(x%i == 0)return 0;
	}return 1;
}long long mod[10];
bitset<30000005>x[4];
long long a[12];
const long long base = 71;
inline int calc(int x){
	long long sum = 0;
	for(int i = 1;i<=8;i++){
	//	cout << a[i] << endl;
		sum = (sum*base+a[i]);
	}sum%=mod[x];
//	cout << sum << endl;
	return sum;
}
void solve(){
	char s[12];int op;//cout << 111 << endl;

	scanf("%s",s+1);scanf("%d",&op);
	for(int i = 1;i<=8;i++){
		if('0'<=s[i] and s[i]<='9')a[i] = s[i]-'0';
		if('A'<=s[i] and s[i]<='Z')a[i] = 10+s[i]-'A';
		if('a'<=s[i] and s[i]<='z')a[i] = 36+s[i]-'a';
		if(s[i] == '{')a[i] = 63;
		if(s[i] == '|')a[i] = 64;
	}//cout << 111 << endl;

//for(int i = 1;i<=8;i++)a[i] = rand()%65;op = rand()%2;
//	cout << op << endl;
	if(op == 0){
		for(int i =0;i<4;i++)x[i][calc(i)] = 1;	
	}else{
		int ok = 1;
		for(int i =0;i<4;i++)if(!x[i][calc(i)])ok = 0;
		if(ok)putchar('1');else putchar('0');putchar('\n');
	}
}
signed main(){srand(time(0));
	mod[0] = 29998057;
	mod[1] =29998061;
	mod[2] = 29998063;
	mod[3] =29998099;
	int tot =0 ;/*
	for(int i = 29998000;tot<=4;i++){
		if(is_prime(i)){
			tot++;cout << i << endl;
		}
	}*/
	int t ;cin>>t;
	while(t--){
		solve();
	}return 0;
}//