#include <fstream>
#include <iostream>
#include <string>
#include <map>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <cstring>
#include <climits>
#include <deque>
#include <stack>

using namespace std;

#define ONLINE_JUDGE1

int hash1, hash2;
#define P 73
#define MOD1 100007


int mx;
int N, lastpos;
string S;
char palin[100000];
vector <int> PP(50001);

void solve();
void DFS(int iam, int from, vector <vector <int> > &V);

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	int T;
	PP[0] = 1;
	for (int i = 1; i < 50001; ++i) {
		PP[i] = PP[i - 1] * P;
		PP[i] %= MOD;
	}
	cin >> T;
	while (T--) {
		solve();
	}
#ifndef ONLINE_JUDGE
	while (1);
#endif
	return 0;
}


void solve() {
	vector <vector <int> > V;
	cin >> N;
	mx = 0;
	cin >> S;
	int x, y, i;
	V.resize(N + 1);
	for (i = 0; i < N - 1; ++i) {
		cin >> x >> y;
		V[y].push_back(x);
		V[x].push_back(y);
	}
	lastpos = 0;
	mx = 0;
	DFS(1, -1, V);
	cout << mx << '\n';
}

void DFS(int iam, int from, vector <vector <int> > &V) {
	palin[lastpos++] = S[iam - 1];
	int m1, m2;
	/*
	if (lastpos % 2 == 0) {
		m1 = lastpos / 2 - 1;
		m2 = m1 + 1;
	}
	else {
		m1 = lastpos / 2 - 1;
		m2 = lastpos / 2 + 1;
	}
	while (m1 >= 0) {
		if (palin[m1] != palin[m2]) break;
		--m1;
		++m2;
		hash1 = ((hash1 - (B[i - NA] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;

	}
	*/

	if (lastpos % 2 == 0) {
		m1 = lastpos / 2 - 1;
		hash1 = (hash1 * P + palin[m1]) % MOD;
		m2 = m1 + 1;
		hash2 += palin[lastpos / 2 - 1] * PP[lastpos / 2];
		hash2 %= MOD;
	}
	else {

	}

	if (hash1 == hash2) {
		mx = max(mx, lastpos);
	}
	int nx;
	for (int i = V[iam].size() - 1; i >= 0; --i) {
		nx = V[iam][i];
		if (nx != from && nx != iam) {
			DFS(nx, iam, V);
		}
	}
	--lastpos;
}