OnlineJudge 3 现已推出。点此体验新版：Sequence | SDUT OnlineJudge

### Sequence

Time Limit: 1000 ms
Memory Limit: 65536 KiB

#### Problem Description

Given an integer number sequence A of length N (1<=N<=1000), we define f(i,j)=(A[i]+A[i+1]+...+A[j])^2 (i<=j). Now you can split the sequence into exactly M (1<=M<= N) succesive parts, and the cost of a part from A[i] to A[j] is f(i,j). The totle cost is the sum of the cost of each part. Please split the sequence with the minimal cost.

#### Input

At the first of the input comes an integer t indicates the number of cases to follow. Every case starts with a line containing N ans M. The following N lines are A[1], A[2]...A[N], respectively. 0<=A[i]<=100 for every 1<=i<=N.

#### Output

For each testcase, output one line containing an integer number denoting the minimal cost of splitting the sequence into exactly M succesive parts.

#### Sample Input

1 5 2 1 3 2 4 5

#### Sample Output

117

#### Hint

#### Source

山东省第二届ACM大学生程序设计竞赛