#include <bits/stdc++.h>
using namespace std;
int T, n, a[1000010], l[1000010], r[1000010];
int s[1000010][2], len[1000010];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &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);
        for (int b = 1; b <= M; b++) {
            int res = 0;
            int cur = 0;
            for (int i = 1; i <= n; i = r[i]) {
                if (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;
                    }
                }
                else {
                    res += s[i][cur];
                    cur ^= (len[i] & 1);
                }
            }
            printf("%d\n", res);
            for (int i = 1; i <= n; i = r[i])
                if (a[i] == b) {
                    len[i] = 1;
                    s[i][0] = a[i];
                }
            for (int i = 2; i <= n; i = r[i])
                if (len[i] && len[l[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];
                }
        }
    }
}