#include<bits/stdc++.h>

using namespace std;


const int N = 1e5 + 10;

int w[N];

vector<int> edges[N];

bool visited[N];

int cnt = 0;

int f[N];


void dfs(int u) {

        int c = 0;

        visited[u] = true;

        for(int v : edges[u]) {

                if(visited[v]) continue;

                ++c; dfs(v);

        }


        if(!c) ++f[w[u]];

        else if(u != 1 && w[u] == 2) ++cnt;

}


void solve() {

        int n; cin >> n;

        cnt = 0;

        for(int i = 1; i <= n; i++) edges[i].clear(), visited[i] = false;

        for(int i = 1; i < n; i++) {

                int u, v; cin >> u >> v;

                edges[u].push_back(v);

                edges[v].push_back(u);

        }

        string s; cin >> s;

        for(int i = 0; i < n; i++) {

                if(s[i] == '?') w[i + 1] = 2;

                else w[i + 1] = s[i] - '0';

        }


        f[0] = f[1] = f[2] = 0;

        dfs(1);


        int ans = 0;

        if(w[1] == 0) ans = f[1] + (f[2] + 1) / 2;

        if(w[1] == 1) ans = f[0] + (f[2] + 1) / 2;

        if(w[1] == 2 && f[0] == f[1]) ans = f[1] + (f[2] + (cnt % 2)) / 2;

        if(w[1] == 2 && f[0] != f[1]) ans = max(f[0], f[1]) + f[2] / 2;

        cout << ans << '\n';

}


int main() {

        int t; cin >> t;

        while(t--) {

                solve();

        }

}

#include<bits/stdc++.h>

using namespace std;


int w[100010];


void solve() {

        int n, a, b; cin >> n >> a >> b;

        int c = __gcd(a, b);


        for(int i = 1; i <= n; i++) {

                cin >> w[i];

                w[i] %= c;

        }

        sort(w + 1, w + 1 + n);

        int ans = w[n] - w[1];

        for(int i = 1; i < n; i++) {

                ans = min(ans, w[i] + c - w[i + 1]);

        }

        cout << ans << '\n';

}


int main() {

        int t; cin >> t;

        while(t--) {

                solve();

        }