#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 k = 1; k <= n; k++) {
    for(int i = 1; i + k - 1 <= n; i++) {
      int j = i + k - 1;
      for(int v = 0; v <= mx; v++) {
        for(int l = i; l <= j; l++) {
          for(int t = 0; t <= mx && max(a[l], t) / 2 <= v; t++) {
            int w = max(a[l] - t, 0);
            if(i < l)w += f[i][l - 1][t];
            else w += (t == 0 ? 0 : INF);
            if(l < j)w += f[l + 1][j][t];
            else w += (v - max(a[l], t) / 2 == 0 ? 0 : INF);
            // printf("qwq:%d %d %d %d\n", i, j, v, w);
            chkmin(f[i][j][v], w);
            // chkmin(f[i][j][v], f[i][l - 1][t] + f[l + 1][j][v - max(a[l], t) / 2] + 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;
}