#include <cstdio>
#include <cassert>

#include <vector>
#include <algorithm>

using namespace std;

const int BASE = 31;

class Reader {
  public:
    Reader(FILE *_stream, const int _size = (1 << 16)):
      size(_size),
      pointer(0),
      buffer(new char[_size]),
      stream(_stream) {
        assert(fread(buffer, 1, size, stream) != 0);
    }

    template<class IntType>
    IntType NextInt() {
        IntType value = 0;
        bool negative = false;
        while ((Current() < '0' || Current() > '9') && Current() != '-')
            NextPosition();
        if (Current() == '-') {
            negative = true;
            NextPosition();
        }
        while(Current() >= '0' && Current() <= '9') {
            value = value * 10 + Current() - '0';
            NextPosition();
        }
        if (negative)
            value = -value;
        return value;
    }

    char NextToken() {
        while (Current() == ' ' || Current() == '\n' || Current() == '\0')
            NextPosition();
        char token = Current();
        NextPosition();
        return token;
    }

    Reader &operator>>(int &value) {
        value = NextInt<int>();
        return *this;
    }

    Reader &operator>>(char &token) {
        token = NextToken();
        return *this;
    }

  private:
    int size, pointer;
    char *buffer;
    FILE *stream;

    char Current() const {
        return buffer[pointer];
    }

    void NextPosition() {
        if(++pointer == size) {
            assert(fread(buffer, 1, size, stream) != 0);
            pointer = 0;
        }
    }
};

class Key {
  public:
    Key(const int value = 0) {
        for (int i = 0; i < U_COUNT; ++i)
            values[i] = value % U[i];
    }

    Key operator=(const Key &other) {
        for (int i = 0; i < U_COUNT; ++i)
            values[i] = other.values[i];
        return *this;
    }

    Key operator=(const int value) {
        return *this = Key(value);
    }

    Key operator+(const Key &other) const {
        Key result;
        for (int i = 0; i < U_COUNT; ++i)
            result.values[i] = (values[i] + other.values[i]) % U[i];
        return result;
    }

    Key operator+(const int value) const {
        return *this + Key(value);
    }

    Key operator*(const Key &other) const {
        Key result;
        for (int i = 0; i < U_COUNT; ++i)
            result.values[i] = (1LL * values[i] * other.values[i]) % U[i];
        return result;
    }

    Key operator*(const int value) const {
        return *this * Key(value);
    }

    bool operator==(const Key &other) const {
        for (int i = 0; i < U_COUNT; ++i)
            if (values[i] != other.values[i])
                return false;
        return true;
    }

    bool operator==(const int value) const {
        return *this == Key(value);
    }

  private:
    static const int U_COUNT = 4;
    static const int U[U_COUNT];

    int values[U_COUNT];
};

const int Key::U[Key::U_COUNT] = {666013, 1000003, 1000000007, 1000000009};

class Tree {
  public:
    static const int NIL = -1;

    Tree(const int _v = 0, const int _root = NIL):
      v(_v),
      root(_root),
      edges(vector< vector<int> >(_v, vector<int>())),
      values(vector<int>(_v, 0)) {}

    void AddEdge(const int x, const int y) {
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    void SetValue(const int x, const int value) {
        values[x] = value;
    }

    int GetLongestPalindromicPathFromRoot() const {
        return PalindromeDFS(root, NIL, 1, Key(0), Key(0), Key(1));
    }

  private:
    int v, root;
    vector< vector<int> > edges;
    vector<int> values;

    int PalindromeDFS(const int x, const int father, const int depth, Key hash, Key reverseHash, Key basePower) const {
        hash = hash + basePower * values[x];
        reverseHash = reverseHash * BASE + values[x];
        int maxPalindrome = 0;
        if (hash == reverseHash)
            maxPalindrome = depth;
        for (vector<int>::const_iterator y = edges[x].begin(); y != edges[x].end(); ++y)
            if (*y != father)
                maxPalindrome = max(maxPalindrome, PalindromeDFS(*y, x, depth + 1, hash, reverseHash, basePower * BASE));
        return maxPalindrome;
    }
};

int main() {
    //assert(freopen("palarb.in", "r", stdin));
    //assert(freopen("palarb.out", "w", stdout));
    Reader in = Reader(stdin);
    int testCount;
    in >> testCount;
    for (; testCount > 0; --testCount) {
        int v;
        in >> v;
        Tree tree = Tree(v, 0);
        for (int x = 0; x < v; ++x) {
            char symbol;
            in >> symbol;
            tree.SetValue(x, int(symbol - 'a') + 1);
        }
        for (int i = 1; i < v; ++i) {
            int x, y;
            in >> x >> y;
            tree.AddEdge(x - 1, y - 1);
        }
        printf("%d\n", tree.GetLongestPalindromicPathFromRoot());
    }
    return 0;
}