#include<bits/stdc++.h>
#define rep(i,a,b) for (register int i=(a);i<=(b);i++)
#define drep(i,a,b) for (register int i=(a);i>=(b);i--)
typedef long long ll;
using namespace std;

template<typename T1,typename T2> inline void chkmin(T1 &x,const T2 &y){x=(x<y)?x:y;}
template<typename T1,typename T2> inline void chkmax(T1 &x,const T2 &y){x=(x>y)?x:y;}

const int N=75,M=160,lim=150;

int n,a[N],f[N][N][M];

void solve()
{
	cin>>n;
	rep(i,1,n) cin>>a[i];
	 
	memset(f,0x3f,sizeof(f));
	rep(i,1,n) f[i][i][a[i]/2]=a[i];
	
	rep(len,2,n) rep(l,1,n-len+1)
	{
		int r=l+len-1;
		rep(v,0,lim) chkmin(f[l][r][max(v,a[r])/2],f[l][r-1][v]+max(0,a[r]-v));
		rep(k,l,r-1)
		{
			rep(v0,0,lim) if (f[l][k][v0]<1e9) rep(v1,0,lim-v0) if (f[k+1][r][v1]<1e9)
			{
				chkmin(f[l][r][v0+v1],f[l][k][v0]+f[k+1][r][v1]);
			} 
		}
	}
	
	rep(i,1,n)
	{
		int ans=1e9;
		rep(j,0,lim) chkmin(ans,f[1][i][j]);
		printf("%d ",ans);
	}
	printf("\n");
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	
	int sid,T; cin>>sid>>T;
	while (T--) solve();
	
	return 0;
}