#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ll long long
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        ll mx = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            if ((ll)a[i] > mx) mx = a[i];
        }
        
        vector<int> b;
        b.reserve(n);
        for (int i = 0; i < n; ++i) {
            if (a[i] <= n) b.push_back(a[i]);
        }
        sort(b.begin(), b.end());
        
        int m = 0;
        for (int x : b) {
            if (x == m) ++m;
            else if (x > m) break;
        }
        
        if (m == 0) {
            cout << (ll)n * mx << '\n';
            continue;
        }
        
        ll best = 0;
        for (int k = 0; k <= m; ++k) {
            ll kk = k;
            ll mm = m;
            ll nn = n;
            ll cur;
            if (k == m) {
                cur = mm * mm + (nn - mm) * (mm + mx);
            } else {
                ll sumMex = kk * kk;
                ll sumFromKtoM = (mm + kk) * (mm - kk + 1) / 2;
                cur = sumMex + sumFromKtoM + mm * (nn - mm - 1) + (nn - kk) * mx;
            }
            if (cur > best) best = cur;
        }
        
        cout << best << '\n';
    }
    
    return 0;
}