#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    const auto query = [&](const vector<int64_t> &p, int l, int r) -> int64_t {
        if (l > r) return 0;
        return p[r + 1] - p[l];
    };

    vector<int64_t> pre0(n + 1);
    vector<int64_t> pre1(n + 1);
    for (int i = 0; i < n; i++) {
        pre0[i + 1] = pre0[i] + (i & 1 ? 0 : a[i]);
        pre1[i + 1] = pre1[i] + (~i & 1 ? 0 : a[i]);
    }

    const int M = *max_element(a.begin(), a.end());

    int head = 0;
    vector<int> nxt(n);
    vector<int> prv(n);
    iota(nxt.begin(), nxt.end(), 1);
    iota(prv.begin(), prv.end(), -1);

    for (int x = 1; x <= M; x++) {
        int64_t ans = 0;

        vector<int> to_delete;
        int cur = 0;

        {
            int64_t sum = query(pre1, 0, head - 1);
            ans += sum;
            cur += head;
        }

        for (int i = head; i < n; i = nxt[i]) {
            debug(x, i);
            if (a[i] == x) {
                to_delete.emplace_back(i);
            }
            int64_t q = a[i] / x, r = a[i] % x;
            if (cur & 1) {
                ans += q / 2 * x + (q % 2 ? r : 0);
            } else {
                ans += (q + 1) / 2 * x + (q % 2 ? 0 : r);
            }
            cur += q + (r != 0);
            {
                int64_t sum;
                if ((cur ^ i) & 1)
                    sum = query(pre0, i + 1, nxt[i] - 1);
                else
                    sum = query(pre1, i + 1, nxt[i] - 1);
                ans += sum;
                cur += nxt[i] - i - 1;
                debug(sum, i, nxt[i], cur);
            }
        }

        for (int z: to_delete) {
            int l = prv[z];
            int r = nxt[z];
            if (l != -1)
                nxt[l] = r;
            if (r != n)
                prv[r] = l;
            if (z == head)
                head = r;
        }

        cout << ans << '\n';
    }

}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--)
        solve();

    return 0;
}