#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=210,lim=200;

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

void solve()
{
	cin>>n;
	rep(i,1,n) cin>>a[i];
	 
	memset(f,0x3f,sizeof(f));
	memset(g,-0x3f,sizeof(g));
	rep(i,1,n)
	{
		rep(j,0,a[i]) f[i][i][j]=a[i]-j,g[i][i][j]=a[i];
		rep(j,a[i]+1,lim) f[i][i][j]=0,g[i][i][j]=j;
	}
	
	rep(len,2,n) rep(l,1,n-len+1)
	{
		int r=l+len-1;
		rep(v,0,lim)
		{
			auto upd=[&](int v0,int v1)
			{
				if (v0<f[l][r][v]) f[l][r][v]=v0,g[l][r][v]=v1;
				else if (v0==f[l][r][v]) chkmax(g[l][r][v],v1);
			};
			
			int dn=max(v,a[l])/2,coef=max(0,a[l]-v);
			upd(coef+f[l+1][r][min(lim,dn)],g[l+1][r][min(lim,dn)]);
			rep(k,l+2,r)
			{
				int dn2=g[l+1][k-1][0]/2;
				upd(coef+f[l+1][k-1][0]+f[k][r][min(lim,dn+dn2)],g[k][r][min(lim,dn+dn2)]);
			}
		}
	}
	
	rep(i,1,n) printf("%d ",f[1][i][0]);
	printf("\n");
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
//	freopen("data.in","r",stdin);
	
	int sid,T; cin>>sid>>T;
	while (T--) solve();
	
	return 0;
}