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

using namespace std;

const int NMAX = 150000;

char s[NMAX+2];
int ad[NMAX+2];
int viz[NMAX+2];
int lgmax= 1;
int T, N;

vector <int> g[NMAX+2];
vector <int> v,dub;

inline void init() {
    lgmax= 1;
    for( int i= 1;  i<=NMAX;  ++i ) {
        g[i].clear();
        viz[i]= 0;
    }
    v.clear();
}

void dfs(int nod){
    int lg= (int)g[nod].size();

    v.push_back( ad[ nod ] );
    dub= v;
    reverse( dub.begin(), dub.end() );
    if( dub == v ) {
        lgmax= max( lgmax, (int)dub.size() );
    }

    for(int i= 0;  i<lg;  i++){
        if( viz[ g[nod][i] ]==0 ){
            viz[ g[nod][i] ]= 1;
            dfs( g[ nod ][i] );
        }
    }

    v.pop_back();
}


inline void Rezolva() {
    dfs( 1 );
    cout << lgmax << '\n';
}

int main()
{

    cin >> T;
    for( int t= 0;  t<T; ++t ) {
        init();
        cin >> N;
        cin >> s;
        for( int i= 0;  i<N; ++i ) {
            ad[ i+1 ]= s[i]-'a';
        }
        for( int i= 1;  i<N;  ++i ) {
            int a,b;
            cin >> a >> b;
            g[a].push_back( b );
            g[b].push_back( a );
        }
        Rezolva();
    }
    return 0;
}