#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <fstream>

using namespace std;
//ifstream f("a.in");
//#define cin f
#define rrrr 500000
char  s[rrrr];
int p[rrrr];
pair <int,int> ad[rrrr];
int t,n,i,x,y,a,q[rrrr],l;
bool viz[rrrr];
vector <int> v[rrrr];
//#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]].first=ad[nod].first+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(),ad[i].second=i;
        memset(viz,0,n+10);
        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;
        sort(ad+1,ad+n+1);
        i=n;
        while (1)
        {
            while (s[ad[i].second]!=s[1])--i;
            if (!palind(ad[i].second)) --i;
            else break;
        }
            cout<<ad[i].first+1<<'\n';
            //if (t==1) for (i=1;i<=n;++i) cout<<p[i]<<' ';

    }
    return 0;
}