#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;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDx1bm9yZGVyZWRfbWFwPgojaW5jbHVkZSA8Y21hdGg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1pblN0cmluZ1ZhbHVlKGludCBLLCBjb25zdCBzdHJpbmcmIFMpIHsKICAgIHZlY3RvcjxpbnQ+IGZyZXEoMjYsIDApOwogICAgZm9yIChjaGFyIGNoIDogUykgewogICAgICAgIGZyZXFbY2ggLSAnQSddKys7CiAgICB9CgogICAgcHJpb3JpdHlfcXVldWU8aW50PiBwcTsKICAgIGZvciAoaW50IGYgOiBmcmVxKSB7CiAgICAgICAgaWYgKGYgPiAwKSBwcS5wdXNoKGYpOwogICAgfQoKICAgIHdoaWxlIChLLS0gJiYgIXBxLmVtcHR5KCkpIHsKICAgICAgICBpbnQgdG9wID0gcHEudG9wKCk7IHBxLnBvcCgpOwogICAgICAgIHRvcC0tOwogICAgICAgIGlmICh0b3AgPiAwKSBwcS5wdXNoKHRvcCk7CiAgICB9CgogICAgaW50IHJlc3VsdCA9IDA7CiAgICB3aGlsZSAoIXBxLmVtcHR5KCkpIHsKICAgICAgICBpbnQgZiA9IHBxLnRvcCgpOyBwcS5wb3AoKTsKICAgICAgICByZXN1bHQgKz0gZiAqIGY7CiAgICB9CgogICAgcmV0dXJuIHJlc3VsdDsKfQoKaW50IG1haW4oKSB7CiAgICBpbnQgVDsKICAgIGNpbiA+PiBUOwogICAgd2hpbGUgKFQtLSkgewogICAgICAgIGludCBLOwogICAgICAgIHN0cmluZyBTOwogICAgICAgIGNpbiA+PiBLID4+IFM7CiAgICAgICAgY291dCA8PCBtaW5TdHJpbmdWYWx1ZShLLCBTKSA8PCBlbmRsOwogICAgfQogICAgcmV0dXJuIDA7Cn0=

MgoKMAoKQUJDQwoKMQoKQUJDQw==

2

0

ABCC

1

ABCC