#include <bits/stdc++.h>

#define ndl '\n'
#define ll long long
#define INF 1000000007
#define debug(x) cout << #x << ": " << x << ndl
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()

using namespace std;

struct SegTree {
    int n;
    vector<ll> p, np, dl;
    SegTree(int x) {
        for(n = 1; n < x; n<<=1);
        p.assign(n<<1, 0);
        np.assign(n<<1, 0);
        dl.assign(n<<1, 0);
    }
    void set(int ind, int p_i, int np_i, int dl_i) {
        ind += n;
        p[ind] = p_i;
        np[ind] = np_i;
        dl[ind] = dl_i;
        for(int i = ind>>1; i>0; i>>=1) {
            dl[i] = dl[i*2] + dl[i*2+1];
            if(dl[i*2]&1) {
                np[i] = np[i*2] + p[i*2+1];
                p[i] = p[i*2] + np[i*2+1];
            } else {
                np[i] = np[i*2] + np[i*2+1];
                p[i] = p[i*2] + p[i*2+1];
            }
        }
    }
};

tuple<int, int, int> get_sums(int a, int b) {
    int p, np, dl;
    dl = (a + b - 1) / b;
    int mod_elem = (a - 1) % b + 1;
    p = b * ((dl - 1) / 2) + (!(dl&1)?mod_elem:0);
    np = b * (dl / 2) + (dl&1?mod_elem:0);
    return {p, np, dl};
}

void rob() {
    int n, maxi = 1; cin>>n;
    SegTree st(n);
    set<pair<int, int>> zest;
    for(int i=0;i<n;i++) {
        int a; cin>>a;
        maxi = max(maxi, a);
        zest.insert({i, a});
    }
    for(int b=1;b<=maxi;b++) {
        for(auto [i, a]: zest) {
            if(a < b) {
                zest.erase({i, a});
                continue;
            }
            auto [p, np, dl] = get_sums(a, b);
            st.set(i, p, np, dl);
        }
        cout<<st.np[1]<<'\n';
    }

}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
        rob();
}