Word Wrap Problem Statement

You are tasked with arranging 'N' words of varying lengths such that each line contains at most 'M' characters, with each word separated by a space. The challenge is to minimize the cost, where the cost of each line is calculated as the cube of the extra space characters needed to reach 'M' characters. The total cost is the sum of all line costs.

Your Goal

Minimize the total cost to achieve this arrangement and return the minimum total cost.

Input:

The first line of input contains an integer ‘T’, representing the number of test cases. For each test case: 
The first line contains two positive integers, ‘N’ and ‘M’, where 'N' is the number of words and 'M' is the maximum number of characters allowed per line. 
The following 'N' lines each contain one word.

Output:

For each test case, output a single line containing an integer, which represents the minimum cost to arrange the words according to the specified conditions.

Example:

Input:

2
4 10
word1
word2
word3
word4
5 8
worda
wordb
wordc
wordd
worde

Output:

XYZ
ABC

Constraints:

• 1 <= T <= 100
• 1 <= N <= 300
• 1 <= |words[i]| <= 100
• 1 <= M <= 100
• Time Limit: 1 sec

Note:

The length of each word must be ≤ 'M'.
You cannot break a word across lines. Each word must appear fully on one line.