#include <stdio.h>
#include <vector>
#define NMAX 100010

using namespace std;

char val[NMAX];
int N, T;
int tata[NMAX];
vector <pair <int, int> > V;
vector <pair <int, int> >::iterator it;
vector <int> noduri[NMAX];
pair <int, int> D;
vector <int> G[NMAX];
int niv[NMAX];

int search (int a, int b) {
    b = tata[b];
    int ok = 0, x;
    if (a == b) ok = 1;
    for (int i = 0; i < G[a].size(); ++i) {
        x = G[a][i];
        if (val[x] == val[b] && niv[x] <= niv[b]) {
            if (x == b) {
                ok = 1;
                break;
            }
            if (tata[b] == x) {
                ok = 1;
                break;
            }
            else ok = search (x, b);
        }
    }
    return ok;
}

int main() {
    //freopen ("palarb.in", "r", stdin);
    int x, y;
    scanf ("%d", &T);
    int i;
    while (T--) {
        //prealabil -------------
        scanf ("%d", &N);
        for (i = 0; i <= N; ++i)
            scanf ("%c", &val[i]), tata[i] = 0, niv[i] = 0, noduri[i].clear(), G[i].clear();
        tata[1] = -1;
        for (i = 1; i < N; ++i) {
        scanf ("%d %d", &x, &y);
        if (tata[x]) {
            tata[y] = x;
            niv[y] = niv[x] + 1;
            noduri[niv[y]].push_back(y);
            continue;
        }
        if (tata[y]) {
            tata[x] = y;
            niv[x] = niv[y] + 1;
            noduri[niv[x]].push_back(x);
            continue;
        }

        V.push_back(make_pair(x, y));
    }
    while (!V.empty()) {
        for (it = V.begin(); it != V.end(); ++it) {
            D = *it;
            x = D.first;
            y = D.second;
            if (tata[x]) {
                tata[y] = x;
                niv[y] = niv[x] + 1;
                noduri[niv[y]].push_back(y);
                V.erase(it);
                break;
            }
            if (tata[y]) {
                tata[x] = y;
                niv[x] = niv[y] + 1;
                noduri[niv[x]].push_back(x);
                V.erase(it);
                break;
            }
        }

    }
    for (i = 2; i <= N; ++i)
        G[tata[i]].push_back(i);

        //------------

        int maxim = 1;

        for (i = 2; i <= N; ++i) {
            if (val[i] == val[1]) {
                if(search (1, i)) {
                    x = niv[i] + 1;
                    if (x > maxim) maxim = x;
                }
            }
        }
        printf ("%d\n", maxim);
    }
    return 0;
}