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

using namespace std;

const int P[] = {43, 53, 61};

int T, N;
char A[100010];
vector<int> V[100010];
int niv[100010];
bool S[100010];
int result;

int H[3], Hn[3], powr[3];
int oH[100010][3], oHn[100010][3], opowr[100010][3];

void Dfs(int x)
{
	bool ok = true;
	for (int p = 0; p < 3; ++p)
		if (H[p] != Hn[p])
			ok = false;
	if (ok) result = max(result, niv[x]);

	S[x] = true;

	for (vector<int>::iterator it = V[x].begin(); it != V[x].end(); ++it)
		if (!S[*it])
		{
			for (int p = 0; p < 3; ++p)
			{
				oH[x][p] = H[p];
				oHn[x][p] = Hn[p];
				opowr[x][p] = powr[p];

				H[p] = H[p] * P[p] + (A[*it] - 'a' + 1);
				powr[p] = powr[p] * P[p];
				Hn[p] = Hn[p] + powr[p] * (A[*it] - 'a' + 1);
			}

			niv[*it] = niv[x] + 1;
			Dfs(*it);

			for (int p = 0; p < 3; ++p)
			{
				H[p] = oH[x][p];
				Hn[p] = oHn[x][p];
				powr[p] = opowr[x][p];
			}
		}
}

int main()
{
	cin.sync_with_stdio(false);

	cin >> T;
	while (T--)
	{
		memset(S, 0, sizeof(S));

		result = 1;
		for (int i = 1; i <= 100000; ++i)
			V[i].clear();

		cin >> N;
		cin >> (A + 1);

		for (int i = 1, nod1, nod2; i < N; ++i)
		{
			cin >> nod1 >> nod2;

			V[nod1].push_back(nod2);
			V[nod2].push_back(nod1);
		}

		for (int p = 0; p < 3; ++p)
		{
			H[p] = (A[1] - 'a' + 1);
			Hn[p] = (A[1] - 'a' + 1);
			powr[p] = 1;
		}

		niv[1] = 1;
		Dfs(1);

		cout << result << '\n';

        if (N == 100000) break;
	}
}