#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 1000010;
int n, m, ans;
int h[N], e[N], ne[N], idx;
int w[N], v[N];
char c[N];
int stk[N], top;
int f[N][2];
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs1(int u)
{
if (!c[u]) return v[u];
if (c[u] == '!') w[u] = !dfs1(e[h[u]]);
else
{
int a = e[h[u]], b = e[ne[h[u]]];
if (c[u] == '&') w[u] = dfs1(a) & dfs1(b);
else w[u] = dfs1(a) | dfs1(b);
}
return w[u];
}
void dfs2(int u) {
if (!c[u]) {
f[u][v[u]] = 0, f[u][v[u] ^ 1] = 1;
return;
}
f[u][w[u]] = 0;
int a = e[h[u]], b = e[ne[h[u]]];
dfs2(a), dfs2(b);
if (c[u] == '&') {
if (w[u] == 0)
f[u][w[u] ^ 1] = f[a][1] + f[b][1];
else
f[u][w[u] ^ 1] = min(f[a][0] + f[b][0], min(f[a][1] + f[b][0], f[a][0] + f[b][1]));
}
else {
if (w[u] == 0)
f[u][w[u] ^ 1] = min(f[a][1] + f[b][0], min(f[a][1] + f[b][1], f[a][0] + f[b][1]));
else
f[u][w[u] ^ 1] = f[a][0] + f[b][0];
}
}
int main()
{
int T;
cin >> T;
while (T -- ) {
memset(h, -1, sizeof h);
idx = 0, top = 0;
memset(f, 0, sizeof f);
cin >> n;
m = n;
string s;
getchar();
getline(cin, s);
for (int i = 1; i <= n; i ++ ) cin >> v[i];
for (int i = 0; i < s.size(); i ++ )
{
if (s[i] == ' ') continue;
if (s[i] == 'x')
{
int j = i + 1, x = 0;
while (j < s.size() && isdigit(s[j])) x = x * 10 + s[j ++ ] - '0';
stk[ ++ top] = x;
i = j;
}
else
{
c[ ++ m] = s[i];
add(m, stk[top -- ]);
add(m, stk[top -- ]);
stk[ ++ top] = m;
}
}
ans = dfs1(m);
dfs2(m);
cout << f[m][ans ^ 1] << endl;
}
return 0;
}