#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<queue>
#define in cin
#define out cout
#define abs(x) ((x>0)?(x):(-(x)))
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define DOWNFOR(i, a, b) for(int i = a; i >= b; --i)
#define FOREACH(i, t) for (typeof(t.begin()) i = t.begin(); i != t.end(); ++i)
#define ll long long
using namespace std;
const int Nmax = 100005;
vector<int> G[Nmax];
int T[Nmax],A[Nmax],C[Nmax];
int E[Nmax],K;
int m[Nmax];
int pi[Nmax];
int N;
void Dfs(int x){
    m[x]=1;
    E[++K]=C[x];
    FOREACH(it,G[x]) if(!m[*it]) T[*it]=x,A[x]=1,Dfs(*it);
}
int get(int A[]){
    for(int i=1;i<=N;i++) A[i+N]=A[N-i+1];
    N=2*N;
    for(int i=0;i<N;i++) A[i]=A[i+1];
    int k=0;
    for(int i=1;i<N;i++){
        while(k>0 && A[k]!=A[i]) k=pi[k-1];
        if(A[k]==A[i]) k++;
        pi[i]=k;
    }
    int Max=0;
    for(int i=0;i<N;i++) Max=max(Max,pi[i]);
    return Max;
}
int main(){
    #ifndef ONLINE_JUDGE
    ifstream in("test.in");
    ofstream out("test.out");
    #endif
    int t;
    in>>t;
    for(;t;--t){K=0;
        memset(T,0,sizeof(T));
        memset(A,0,sizeof(A));
        memset(m,0,sizeof(m));
        memset(pi,0,sizeof(pi));
        memset(E,0,sizeof(E)); K=0;
        in>>N;
        string s;
        in>>s;
        FOR(i,1,N){
            C[i]=s[i-1]-'a'+1;
        }
        for(int i = 1; i <= N; ++i) G[i].clear();
        for(int i = 1; i <= N-1; ++i){
            int x,y;
            in>>x>>y;
            G[x].push_back(y);
            G[y].push_back(x);
        }
        Dfs(1);
        out<<get(E)<<'\n';
    }
    return 0;
}