#include <bits/stdc++.h>
using namespace std;
int t, n, a[205], f[205][205], maxn[205][205];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0)	;
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			maxn[i][i] = a[i];
		}
		for (int len = 2; len <= n; len++) {
			for (int i = 1, j = len; j <= n; j++, i++) {
				maxn[i][j] = max(maxn[i][j - 1], maxn[i + 1][j]);
			}
		}
		memset(f, 0, sizeof(f));
		for (int i = 1; i <= n; i++) {
			f[i][0] = f[i - 1][0] + a[i];
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				f[i][j] = max(f[i][j - 1], f[i - 1][j] + a[i]);
				for (int k = 1; k < i; k++) {
					if ((i - k + 1) / 2 > j) continue;
					f[i][j] = max(f[i][j], f[k - 1][j - (i - k + 1) / 2] + maxn[k][i] * (i - k + 1));
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			cout << f[n][i] << " ";
		}
		cout << "\n";
	}
}