#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
ll n;
int main() {
	cin>>n;
	while(n--) {
		string s;
		stack<ll> d;
		cin>>s;
		for(int i=0; i<s.size(); i++) {
			if(s[i]>='0'&&s[i]<='9') {
				d.push(s[i]-'0');
			} else {
				if(s[i]=='!') {
					ll x=d.top();
					d.pop();
					d.push(!x);
				} else if(s[i]=='&') {
					ll a=d.top();
					d.pop();
					ll b=d.top();
					d.pop();
					d.push(a&b);
				} else {
					ll a=d.top();
					d.pop();
					ll b=d.top();
					d.pop();
					d.push(a|b);
				}
			}
		}
		cout<<d.top()<<endl;
	}
	return 0;
}