#include <fstream>
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;

//ifstream F("p.in");
//ofstream G("p.out");

#define F cin
#define G cout

const int Nmax = 100010;
const int M = (1<<30)-1;
const int S = 27;
const int cst = 3;

int P[Nmax],N,Sol;
int P2[Nmax];
vector<int> A[Nmax];
char C[Nmax];
int r[30];

#define IT(type) vector<type>::iterator

void Get(int Nod,int Lvl,int Dad,int Hash1,int Hash2,int hash1,int hash2)
{
    if ( Hash1 == Hash2 && hash1 == hash2 ) Sol = max(Sol,Lvl);
    for (IT(int) it=A[Nod].begin();it!=A[Nod].end();++it)
        if ( *it != Dad )
            Get( *it , Lvl+1 , Nod , (Hash1+P[Lvl]*C[*it])&M , (Hash2*S+C[*it])&M , (hash1+P[Lvl]*r[C[*it]])&M , (hash2*S+r[C[*it]])&M);
}

void solve()
{
    F>>N;
    F>>(C+1);
    for (int i=1;i<=N;++i)
        C[i] -= 'a'-1;
    for (int i=1,a,b;i<N;++i)
    {
        F>>a>>b;
        A[ a ].push_back( b );
        A[ b ].push_back( a );
    }
    P[0] = 1;
    #define random(i,n) ( rand()%(n-i+1)+(i-1) )
    Sol = 0;
    for (int i=1;i<=26;++i)
        r[i] = i;
    for (int i=1;i<=26;++i)
        swap(r[i],r[random(i,26)]);
    for (int i=1;i<=N;++i)
        P[i]= ( P[i-1] * S ) & M;
    Get(1,1,0,C[1],C[1],r[C[1]],r[C[1]]);
    G<<Sol<<'\n';
    for (int i=1;i<=N;++i)
        vector<int>().swap(A[i]);
    memset(C,0,sizeof(C));
}

int T;

int main()
{
    srand(time(0));
    F>>T;
    while ( T-- )
        solve();
}