An IT company decided to publish an internal newsletter describing the projects that have been successfully completed. Each department submits a text paragraph that will be printed in a corresponding designated box of the newsletter. Let’s assume that the paragraph contains only characters a...z and spaces (ASCII code is 32) in several lines, and a word is defined to be the longest sequence of non-space characters on a line.

The printing has to satisfy the following rules:

• Text will be printed in a fixed-width font (meaning that every character occupies a fixed size width) from left to right and going down to the next line at the end of every line.
• The number of printed characters in every line must be the same.
• Words are printed in the box in the same order as they appear in the given paragraph. A word cannot be split or printed on more than one line.
• Consecutive words on the same line are separated by exactly one space.
• Every line contains only words from the original paragraph and spaces.
• Any line that starts with a space must contain only spaces.

The newsletter editor wants to formally assess the prettiness level of a paragraph printing by defining the unbalance of it as the sum of the cubes of the number of space characters at the end of each line including lines containing only spaces. The smaller the unbalance, the prettier the paragraph printing is.

Consider the following example where the paragraph is printed in a box with three lines and each line has a 20-characters width in two ways:

aaa bbbbbbbbb c dddd
eeeeeee ffffff
ggggggggg		

aaa bbbbbbbbb      
c dddd eeeeeee       
ffffff ggggggggg

In this example, the unbalance of the paragraph printing on the left is 0^3 + 6^3 + 11^3 = 1547 while the unbalance of the paragraph printing on the right is 7^3 + 6^3 + 4^3 = 623. The paragraph printing on the right is considered prettier.

Given a text paragraph and a box to be printed, your task is to write a program to find the prettiest printing that has the smallest unbalance.

Input

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each data set, the first line contains an integer L (0 < L ≤ 100) representing the number of lines in the designated box. The second line contains an integer W (0 < W ≤ 1000) representing the number of characters width of the box. The remaining lines contain the paragraph with no more than 1000 words ended with a blank line.

Output

For each data test, write on one line the corresponding unbalance of the prettiest paragraph printing in the designated box. Write -1 in case there does not exist any way to print the paragraph in the designated box.

Example

Sample Input
3
3
20
aaa bbbbbbbbb 
c dddd
eeeeeee ffffff
ggggggggg
2
5
abcde abcde
2
5
abcde abcde
a
Sample Output
623
0
-1