#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_JUDGE

int mx;
int N, lastpos;
string S;
char palin[100000];

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;
	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;
	}
	if (m1 == -1) {
		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;
}