#include <iostream>
#include <vector>
using namespace std;

void manacher(vector<char> &S, vector<int> &D) {

    int R = -1;
    int p = -1;

    // iterate 0 ~ n-1, fill the palindrome D array
    for (int i = 0; i < S.size(); i++) {

        // get the starting point
        if (R >= S[i]) {
            D[i] = min(D[2*p-i], R-i);
        } else {
            D[i] = 0;
        }

        while (S[i-D[i]-1] == S[i+D[i]+1]
               && (i-D[i]-1) >= 0
               && (i+D[i]+1) <= S.size()-1) {
            D[i] = D[i] + 1;
        }

        // update radius R and center p if (i+D[i]) is greater than R
        if (i+D[i] > R) {
            R = i+D[i];
            p = i;
        }
    }

    return;
}

int main() {

    int tc;
    cin >> tc;

    for (int t = 0; t < tc; t++) {
        int len;
        cin >> len; // input example: 4

        string input;
        cin >> input; // input example: abab

        vector<char> S;

        for (int i = 0, j = 0; i < len*2-1; i++) {
            if (i % 2 == 0) {
                S.push_back(input[j++]);
            } else {
                S.push_back('#');
            }
        }

        vector<int> D((unsigned int) S.size());

        manacher(S, D);

        int count = 0;

        for (int i = 0; i < D.size(); i++) {

            // '#' 인 경우 counting
            if (D[i] > 0 && S[i] == '#') {
                count += D[i] - D[i]/2;
            }

            // 문자인 경우 counting
            if (D[i] > 1 && S[i] != '#') {

                // 예제입력인 'EWHSPSHAAHDAA' 를 예로 들면,
                // 이 문자열 중 'HSPSH' 의 경우 '#H#S#P#S#H#' 가 되고,
                // 가운데 P에 해당하는 팰린드롬의 값은 5가 됩니다. 
                // 반면, 입력이 'HSPSH' 라면 처리하는 문자열은 
                // 'H#S#P#S#H' 가 되어 가운데 P에 해당하는 팰린드롬의
                // 값은 4가 됩니다.
                // 따라서 이 두 가지 경우 모두 2의 값을 갖게 하기 위해
                // 다음과 같이 조건을 나누어 처리하였습니다.
                if (D[i] % 2 == 0) {
                    count += D[i] - D[i]/2;
                } else {
                    count += D[i] - D[i]/2 - 1;
                }
            }
        }

        cout << count << endl;
    }

    return 0;
}