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.
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
One integer means the minimum sum of his k friends value.
2 3 3 1 2 3 5 3 5 2 3 8 2
14 138