#include <iostream>
#include <vector>
//#include <fstream>

using namespace std;
//ifstream f("a.in");
//#define cin f
char  s[100010];
int p[100010],ad[100010];
int t,n,i,x,y,a,q[100010],l;
bool viz[100010];
vector <int> v[100010];
void df(int nod)
{
    viz[nod]=true;
    for(int i=0;i<v[nod].size();++i)
    if (!viz[v[nod][i]])
    {
        p[v[nod][i]]=nod;
        ad[v[nod][i]]=ad[nod]+1;
        df(v[nod][i]);
    }
}
bool palind(int nod)
{
    int a=nod;
    l=0;
    while (nod!=1) q[++l]=nod,nod=p[nod];
    q[++l]=1;
    for(int i=1,j=l;i<j;++i,--j) if (s[q[i]]!=s[q[j]]) return false;
    return true;
}
int main()
{
    cin>>t;
    for(;t;--t)
    {

        cin>>n;
        for(i=1;i<=n;++i) v[i].clear(),viz[i]=false,ad[i]=0;

        for(i=1;i<=n;++i)cin>>s[i];
        ad[1]=0;
        for(i=1;i<n;++i)
        {
            cin>>x>>y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        df(1);
        a=-1;
        for(i=1;i<=n;++i) if(s[i]==s[1] && a<ad[i]) if(palind(i))
        {
            a=ad[i];
        }
        cout<<a+1<<'\n';
        //if (t==1) for (i=1;i<=n;++i) cout<<p[i]<<' ';
    }
    return 0;
}