#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi pair<int ,int >
#define pl pair<ll ,ll >
#define pb push_back
#define vl vector <long long int >
#define vi vector <int >
#define vp vector <pi>
#define mod 1000000007
#define eps 1e-9
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define _ <<" "<<
#define forn(x, n) for(int x = 0; x < n ;++ x)
#define forn1n(x,n) for(int x = 1; x <= n ;++ x)
#define forn1(x,n) for(int x = 1; x < n ;++ x)
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#pragma GCC optimize ("Ofast")
void scan(){}
template<typename F, typename... R> void scan(F &f,R&... r){cin>>f;scan(r...);}
int di_; string dnms_, co_ = ",";
void debug_(){cout<<endl;}
template<typename F, typename... R> void debug_(F &f, R&... r){while(dnms_[di_] != ',')cout<<dnms_[di_++];di_++;cout<<": "<<f<<",";debug_(r...);}
#define debug(...) dnms_=#__VA_ARGS__+co_,di_=0,debug_(__VA_ARGS__)
template<class A, class B> ostream& operator<<(ostream& out, const pair<A, B> &a){
return out<<"("<<a.first<<","<<a.second<<")";}
template<class A> ostream& operator<<(ostream& out, const vector<A> &a){
out<<"";for(auto it=a.begin();it!=a.end();it++){if(it!=a.begin())out<<" ";out<<*it;}out<<"";
return out;}
template<class A, class B> istream& operator>>(istream& in, pair<A,B> &a){in>>a.first>>a.second;return in;}
template<class A> istream& operator>>(istream& in, vector<A> &a){for(A &i:a)in>>i;return in;}
struct HASH{
size_t operator()(const pair<int,int>&x)const{
return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
}
};
string s;
vector<string>v;
const int N = 11;
unordered_map<pair<int,int>,vector<int> ,HASH>dp;
bool isop(char ch)
{
return ch == '&'||ch == '|' || ch == '^'; // Check if it is an operator
}
int ansop(int x,int y,char op)
{
// return the resultant after operation
if(op=='|')
return int(x)|int(y);
else if(op=='&')
return int(x)&int(y);
else
return int(x)^int(y);
}
vector<int> solve(int i, int j)
{
if(i==j)
return {stoi(v[i])}; // If we've only one element group then just return it
if(!dp[{i,j}].empty())
return dp[{i,j}]; // memoization
vector<int> pa; // possible answers
for(int k=i+1;k<j;k+=2)
{
assert(isop(v[k][0])); // assure that we're splitting on a operator
vector<int> left = solve(i,k-1); // possible reluts of left group
vector<int> right = solve(k+1,j); // possible results of right grp
for(auto& l:left)
for(auto& r:right)
{
pa.pb(ansop(l,r,v[k][0])); // try every possible combination
}
sort(all(pa));
pa.erase(unique(all(pa)),pa.end()); // remove repeating elements
}
return pa;
}
int main(){
IOS
int t;
cin>>t;
while(t--)
{
cin>>s;
v.clear();
int lindex=0;
forn1(i,s.size())
{
if(isop(s[i]))
{
v.push_back(s.substr(lindex,i-lindex));
v.push_back(s.substr(i,1));
lindex=i+1;
}
}
v.push_back(s.substr(lindex,s.size()-lindex));
auto ans = solve(0,v.size()-1);
cout<<ans.back()<<endl;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBsbCBsb25nIGxvbmcgaW50IAojZGVmaW5lIHBpIHBhaXI8aW50ICxpbnQgPgojZGVmaW5lIHBsIHBhaXI8bGwgLGxsID4KI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSB2bCB2ZWN0b3IgPGxvbmcgbG9uZyBpbnQgPgojZGVmaW5lIHZpIHZlY3RvciA8aW50ID4KI2RlZmluZSB2cCB2ZWN0b3IgPHBpPgojZGVmaW5lIG1vZCAxMDAwMDAwMDA3CiNkZWZpbmUgZXBzIDFlLTkKI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIHNlIHNlY29uZAojZGVmaW5lIGFsbCh4KSB4LmJlZ2luKCksIHguZW5kKCkKI2RlZmluZSBfIDw8IiAiPDwKI2RlZmluZSBmb3JuKHgsCW4pIGZvcihpbnQgeCA9IDA7IHggPCBuIDsrKyB4KSAKI2RlZmluZSBmb3JuMW4oeCxuKSBmb3IoaW50IHggPSAxOyB4IDw9IG4gOysrIHgpCiNkZWZpbmUgZm9ybjEoeCxuKSBmb3IoaW50IHggPSAxOyB4IDwgbiA7KysgeCkKI2RlZmluZSBJT1MgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTtjaW4udGllKDApO2NvdXQudGllKDApOwojcHJhZ21hIEdDQyBvcHRpbWl6ZSAoIk9mYXN0IikKdm9pZCBzY2FuKCl7fQp0ZW1wbGF0ZTx0eXBlbmFtZSBGLCB0eXBlbmFtZS4uLiBSPiB2b2lkIHNjYW4oRiAmZixSJi4uLiByKXtjaW4+PmY7c2NhbihyLi4uKTt9CmludCBkaV87IHN0cmluZyBkbm1zXywgY29fID0gIiwiOwp2b2lkIGRlYnVnXygpe2NvdXQ8PGVuZGw7fQp0ZW1wbGF0ZTx0eXBlbmFtZSBGLCB0eXBlbmFtZS4uLiBSPiB2b2lkIGRlYnVnXyhGICZmLCBSJi4uLiByKXt3aGlsZShkbm1zX1tkaV9dICE9ICcsJyljb3V0PDxkbm1zX1tkaV8rK107ZGlfKys7Y291dDw8IjogIjw8Zjw8IiwiO2RlYnVnXyhyLi4uKTt9CiNkZWZpbmUgZGVidWcoLi4uKSBkbm1zXz0jX19WQV9BUkdTX18rY29fLGRpXz0wLGRlYnVnXyhfX1ZBX0FSR1NfXykKCnRlbXBsYXRlPGNsYXNzIEEsIGNsYXNzIEI+IG9zdHJlYW0mIG9wZXJhdG9yPDwob3N0cmVhbSYgb3V0LCBjb25zdCBwYWlyPEEsIEI+ICZhKXsKICAgIHJldHVybiBvdXQ8PCIoIjw8YS5maXJzdDw8IiwiPDxhLnNlY29uZDw8IikiO30KdGVtcGxhdGU8Y2xhc3MgQT4gb3N0cmVhbSYgb3BlcmF0b3I8PChvc3RyZWFtJiBvdXQsIGNvbnN0IHZlY3RvcjxBPiAmYSl7CglvdXQ8PCIiO2ZvcihhdXRvIGl0PWEuYmVnaW4oKTtpdCE9YS5lbmQoKTtpdCsrKXtpZihpdCE9YS5iZWdpbigpKW91dDw8IiAiO291dDw8Kml0O31vdXQ8PCIiOwoJcmV0dXJuIG91dDt9CnRlbXBsYXRlPGNsYXNzIEEsIGNsYXNzIEI+IGlzdHJlYW0mIG9wZXJhdG9yPj4oaXN0cmVhbSYgaW4sIHBhaXI8QSxCPiAmYSl7aW4+PmEuZmlyc3Q+PmEuc2Vjb25kO3JldHVybiBpbjt9CnRlbXBsYXRlPGNsYXNzIEE+IGlzdHJlYW0mIG9wZXJhdG9yPj4oaXN0cmVhbSYgaW4sIHZlY3RvcjxBPiAmYSl7Zm9yKEEgJmk6YSlpbj4+aTtyZXR1cm4gaW47fQoKc3RydWN0IEhBU0h7CiAgc2l6ZV90IG9wZXJhdG9yKCkoY29uc3QgcGFpcjxpbnQsaW50PiZ4KWNvbnN0ewogICAgcmV0dXJuIGhhc2g8bG9uZyBsb25nPigpKCgobG9uZyBsb25nKXguZmlyc3QpXigoKGxvbmcgbG9uZyl4LnNlY29uZCk8PDMyKSk7CiAgfQp9OwoKc3RyaW5nIHM7CnZlY3RvcjxzdHJpbmc+djsKY29uc3QgaW50IE4gPSAxMTsKdW5vcmRlcmVkX21hcDxwYWlyPGludCxpbnQ+LHZlY3RvcjxpbnQ+ICxIQVNIPmRwOwpib29sIGlzb3AoY2hhciBjaCkKewoJcmV0dXJuIGNoID09ICcmJ3x8Y2ggPT0gJ3wnIHx8IGNoID09ICdeJzsgLy8gQ2hlY2sgaWYgaXQgaXMgYW4gb3BlcmF0b3IKfQoKaW50IGFuc29wKGludCB4LGludCB5LGNoYXIgb3ApCnsKCS8vIHJldHVybiB0aGUgcmVzdWx0YW50IGFmdGVyIG9wZXJhdGlvbgoKCWlmKG9wPT0nfCcpCgkJcmV0dXJuIGludCh4KXxpbnQoeSk7CgllbHNlIGlmKG9wPT0nJicpCgkJcmV0dXJuIGludCh4KSZpbnQoeSk7CgllbHNlCgkJcmV0dXJuIGludCh4KV5pbnQoeSk7Cn0KdmVjdG9yPGludD4gc29sdmUoaW50IGksIGludCBqKQp7CglpZihpPT1qKQoJCXJldHVybiB7c3RvaSh2W2ldKX07IC8vIElmIHdlJ3ZlIG9ubHkgb25lIGVsZW1lbnQgZ3JvdXAgdGhlbiBqdXN0IHJldHVybiBpdAoJaWYoIWRwW3tpLGp9XS5lbXB0eSgpKQoJCXJldHVybiBkcFt7aSxqfV07ICAgIC8vIG1lbW9pemF0aW9uCgl2ZWN0b3I8aW50PiBwYTsgICAgICAgICAgLy8gcG9zc2libGUgYW5zd2VycwoJZm9yKGludCBrPWkrMTtrPGo7ays9MikKCXsKCQkKCQlhc3NlcnQoaXNvcCh2W2tdWzBdKSk7ICAgICAgICAgICAgLy8gYXNzdXJlIHRoYXQgd2UncmUgc3BsaXR0aW5nIG9uIGEgb3BlcmF0b3IKCQl2ZWN0b3I8aW50PiBsZWZ0ID0gc29sdmUoaSxrLTEpOyAgLy8gcG9zc2libGUgcmVsdXRzIG9mIGxlZnQgZ3JvdXAKCQl2ZWN0b3I8aW50PiByaWdodCA9IHNvbHZlKGsrMSxqKTsgLy8gcG9zc2libGUgcmVzdWx0cyBvZiByaWdodCBncnAKCgkJZm9yKGF1dG8mIGw6bGVmdCkKCQkJZm9yKGF1dG8mIHI6cmlnaHQpCgkJCXsKCQkJCXBhLnBiKGFuc29wKGwscix2W2tdWzBdKSk7IC8vIHRyeSBldmVyeSBwb3NzaWJsZSBjb21iaW5hdGlvbgoJCQl9CgkJc29ydChhbGwocGEpKTsKCQlwYS5lcmFzZSh1bmlxdWUoYWxsKHBhKSkscGEuZW5kKCkpOyAvLyByZW1vdmUgcmVwZWF0aW5nIGVsZW1lbnRzCgl9CglyZXR1cm4gcGE7Cn0KaW50IG1haW4oKXsKCUlPUwoKCWludCB0OwoJY2luPj50OwoJd2hpbGUodC0tKQoJewoJCWNpbj4+czsKCQl2LmNsZWFyKCk7CgkJaW50IGxpbmRleD0wOwoJCWZvcm4xKGkscy5zaXplKCkpCgkJewoJCQlpZihpc29wKHNbaV0pKQoJCQkJewoJCQkJCXYucHVzaF9iYWNrKHMuc3Vic3RyKGxpbmRleCxpLWxpbmRleCkpOwoJCQkJCXYucHVzaF9iYWNrKHMuc3Vic3RyKGksMSkpOwoJCQkJCWxpbmRleD1pKzE7CgkJCQl9CgkJfQoJCXYucHVzaF9iYWNrKHMuc3Vic3RyKGxpbmRleCxzLnNpemUoKS1saW5kZXgpKTsKCQlhdXRvIGFucyA9IHNvbHZlKDAsdi5zaXplKCktMSk7CgkJY291dDw8YW5zLmJhY2soKTw8ZW5kbDsKCX0KCXJldHVybiAwOwkKfQ==