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

using namespace std;
//ifstream f("a.in");
//#define cin f
char  s[1000010];
int p[1000010],ad[1000010];
int t,n,i,x,y,a,q[1000010],l;
bool viz[1000100];
vector <int> v[1000010];
#define maxb 16384
char buf[maxb];
int ppp(maxb);
int gi()
{
    int nr=0;
    while (buf[ppp]<'0' || buf[ppp]>'9') if (++ppp>=maxb) cin.read(buf,maxb),ppp=0;
    while (buf[ppp]>='0' && buf[ppp]<='9')
    {
        nr=nr*10+buf[ppp]-'0';
         if (++ppp>=maxb) cin.read(buf,maxb),ppp=0;
    }
    return nr;

}
char gc()
{
     while (buf[ppp]<'a' || buf[ppp]>'z') if (++ppp>=maxb) cin.read(buf,maxb),ppp=0;
     char c=buf[ppp];
     if (++ppp>=maxb) cin.read(buf,maxb),ppp=0;
     return c;

}
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]);
    }
}
inline 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;
    //cout<<t<<'\n';
    for(;t;--t)
    {

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

        cin>>s+1;//,cout<<s[i];
        ad[1]=0;
        //cout<<'\n';
        for(i=1;i<n;++i)
        {
            cin>>x>>y;
            //cout<<x<<' '<<y<<'\n';
            v[x].push_back(y);
            v[y].push_back(x);
        }
        df(1);
        a=-1;
        for(i=n;i>=1;--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;
}