#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define FR first
#define SE second
#define il inline
using namespace std;
inline int read() {
  int x = 0; bool op = 0;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
il bool chkmin(int &a, int b) {return (b < a ? a = b, true : false);}
const int N = 75;
const int M = 155;
const int INF = 1e9;
int n, sid;
int a[N], f[N][N][M];
void solve() {
  n = read();
  for(int i = 1; i <= n; i++)a[i] = read();
  int mx = 0;
  for(int i = 1; i <= n; i++)mx = max(mx, a[i]);
  for(int i = 1; i <= n; i++) {
    for(int j = i; j <= n; j++) {
      for(int v = 0; v <= mx; v++) {
        f[i][j][v] = INF;
      }
    }
  }
  for(int i = 1; i <= n; i++)f[i][i][a[i] / 2] = a[i];
  for(int k = 2; k <= n; k++) {
    for(int i = 1; i + k - 1 <= n; i++) {
      int j = i + k - 1;
      for(int v = 0; v <= mx; v++) {
        if(v >= a[i] / 2)chkmin(f[i][j][v], f[i + 1][j][v - a[i] / 2] + a[i]);
        chkmin(f[i][j][max(v, a[j]) / 2], f[i][j - 1][v] + max(a[j] - v, 0));
        for(int l = i + 1; l < j; l++)if(f[l + 1][j][v] < INF) {
          for(int t = 0; t <= mx && max(a[l], t) / 2 + v <= mx; t++) {
            chkmin(f[i][j][v + max(a[l], t) / 2], f[i][l - 1][t] + f[l + 1][j][v] + max(a[l] - t, 0));
          }
        }
      }
    }
  }
  for(int i = 1; i <= n; i++) {
    int ans = INF;
    for(int v = 0; v <= mx; v++)chkmin(ans, f[1][i][v]);
    printf("%d ", ans);
  }
  putchar('\n');
  return ;
}
int main() { 
  sid = read();
  int test = read();
  while(test--)solve();
  return 0;
}