#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<cmath>
using namespace std;
#define N 1010
#define INF 0 xfffffff
#define LL long long
LL dp[1010];
LL sum[1010];
int a[1010];
int min(int a,int b)
{
if(a<b)
return a;
return b;
}
int main()
{
int t,i,j,n,m,g;
cin>>t;
while(t--)
{
memset(sum,0,sizeof(sum));
cin>>n>>m;
// for(i = 1 ;i <= n ;i++)
//dp[i] = INF;
for(i = 1; i <= n ; i++)
{
cin>>a[i];
sum[i] = sum[i-1]+a[i];
dp[i] = sum[i]*sum[i];
}
for(i = 2; i <= m ; i++) //从2次划分开始到第m次划分
{
for(j = n-m+i ; j >= i ; j--) // 选择能划分i次当然空间
{
for(g = i-1 ; g < j ; g++)
dp[j] = min(dp[j],dp[g]+(sum[j]-sum[g])*(sum[j]-sum[g])); //不断地更新
}
}
cout<<dp[n]<<endl;
}
return 0;
}
/**************************************
Problem id : SDUT OJ 2169
User name : xiaoniu
Result : Accepted
Take Memory : 476K
Take Time : 400MS
Submit Time : 2014-04-21 18:41:26
**************************************/