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

int T,pos,len;
char s[1000005];
int stk[1000005];

void solve()
{
	pos=0;
	scanf("%s",s+1);
	for(len=1;s[len+1]!='\0';len++);
	for(int i=1;i<=len;i++){
		if(s[i]=='0'||s[i]=='1'){stk[++pos]=(s[i]-'0');continue;}
		if(s[i]=='!') {stk[pos]=(!stk[pos]);continue;}
		int R=stk[pos--],L=stk[pos--];
		if(s[i]=='&') stk[++pos]=L&R;
		if(s[i]=='|') stk[++pos]=L|R;
	}
	printf("%d\n",stk[pos]);
}

int main()
{
	scanf("%d",&T);
	while(T--)
		solve();
}