#include <bits/stdc++.h>
using namespace std;
int T, n, a[1000010], l[1000010], r[1000010];
int s[1000010][2], len[1000010];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            l[i] = i - 1;
            r[i] = i + 1;
            s[i][0] = s[i][1] = 0;
            len[i] = 0;
        }
        int M = *max_element(a + 1, a + 1 + n);
        int S = 0;
        for (int b = 1; b <= M; b++) {
            int res = 0;
            int cur = 0;
            for (int i = 1; i <= n; i = r[i]) {
                S++;
                assert(i == 1 || b <= a[i]);
                res += a[i] / b / 2 * b;
                if ((a[i] / b) % 2 == 1) {
                    if (cur == 0) res += b;
                    cur ^= 1;
                }
                if (a[i] % b) {
                    if (cur == 0) res += a[i] % b;
                    cur ^= 1;
                }
                res += s[i][cur];
                cur ^= (len[i] & 1);
            }
            cout << res << "\n";
            for (int i = 2; i <= n; i = r[i]) {
                if (a[i] == b) {
                    swap(s[i][0], s[i][1]);
                    s[i][0] += a[i];
                    len[i]++;
                    if (len[l[i]] % 2 == 0) {
                        s[l[i]][0] += s[i][0];
                        s[l[i]][1] += s[i][1];
                    }
                    else {
                        s[l[i]][0] += s[i][1];
                        s[l[i]][1] += s[i][0];
                    }
                    len[l[i]] += len[i];
                    r[l[i]] = r[i];
                    l[r[i]] = l[i];
                }
            }
        }
        assert(S <= M + accumulate(a + 1, a + 1 + n, 0));
        cerr << S << ' ' << M + accumulate(a + 1, a + 1 + n, 0) << "\n";
    }
}