#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cmath>

using namespace std;

int minStringValue(int K, const string& S) {
    vector<int> freq(26, 0);
    for (char ch : S) {
        freq[ch - 'A']++;
    }

    priority_queue<int> pq;
    for (int f : freq) {
        if (f > 0) pq.push(f);
    }

    while (K-- && !pq.empty()) {
        int top = pq.top(); pq.pop();
        top--;
        if (top > 0) pq.push(top);
    }

    int result = 0;
    while (!pq.empty()) {
        int f = pq.top(); pq.pop();
        result += f * f;
    }

    return result;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int K;
        string S;
        cin >> K >> S;
        cout << minStringValue(K, S) << endl;
    }
    return 0;
}