#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define maxn 100005
using namespace std;

int T,n,sol=-1;
char s[maxn];
vector<int> l[maxn];

void det(int node1,int node2,int f1,int f2,int len)
{
    if(node1==1 || node2==1) sol=max(sol,len);
    for(unsigned int i=0;i<l[node1].size();i++)
     if(l[node1][i]!=f1)
      for(unsigned int j=0;j<l[node2].size();j++)
       if(l[node2][j]!=f2)
        if(s[l[node1][i]]==s[l[node2][j]])
         det(l[node1][i],l[node2][j],node1,node2,len+2);
}

void bfs(int k)
{
    for(unsigned int i=0;i<l[k].size();i++)
      if(s[l[k][i]]==s[k]) det(k,l[k][i],l[k][i],k,2);

    for(unsigned int i=0;i<l[k].size()-1;i++)
     for(unsigned int j=i+1;j<l[k].size();j++)
         if(s[l[k][i]]==s[l[k][j]]) det(l[k][i],l[k][j],k,k,3);
}
void solve()
{
    for(int i=1;i<=n;i++) bfs(i);
}

void read()
{
    int x,y;
    scanf("%d",&T);
    for(int it=1;it<=T;it++)
    {
        scanf("%d\n",&n);
        scanf("%s",s+1);
        for(int i=1;i<=n;i++) l[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            l[x].pb(y); l[y].pb(x);
        }
        sol=-1; solve(); printf("%d\n",sol);
    }
}

int main()
{
    //freopen("pal.in","r",stdin);
    //freopen("pal.out","w",stdout);

    read();

    fclose(stdin);
    fclose(stdout);
    return 0;
}