## Problem Description

Xzz is a child with severe procrastinations. The new semester begins, He still has a lot of homework to do. Now there are K friends help him finish his homework. Xzz has a necklace with n pearl. Now he want to Split into k parts, and send them to these k friends. Each friend will have a value representative how happy they are. And the value is equal the square of sum of the pearl in one part. Now Xzz wants to know minimum sum of his k friends value.

## Input

First line of the input file contains an integer T(0 < T ≤ 20) that indicates how many cases of inputs are there.

The description of each case is given below:

The first line of each case contains two numbers n, k, means there is n pearl necklace and k friends. n, k ≤ 200

Then follow n lines. In ith line there will be n numbers, ai, means the value of ith pearl.1 ≤ ai ≤ 100

## Output

One integer means the minimum sum of his k friends value.

## Sample Input

2
3 3
1 2 3
5 3
5 2 3 8 2

## Sample Output

14
138

## Hint

Each part must be continuous at necklace.

Case 2, three parts are {2, 3}, {8}, {5, 2}

(2 + 3)^2 + 8^2 + (2 + 5)^2

## Source

第九届福建省大学生程序设计竞赛-重现赛（感谢承办泉州师范学院）