This problem is similar but not identical to the problem MORIA.

In the Mines of Moria, the job of Gakrobera Silverborn the dwarf is still to load minecarts with N stones. The stones are numbered, from 1 to N, and a given minecart can only be loaded with consecutive stones.

The minecart have an optimal load L.¹ Each stone has an integer weight between 1 kg and L kg. The score of a minecart loaded with W kg of stones is (W − L)². After all stones have been loaded in minecarts, the total score is the sum of the score of each minecarts. The lower the total score is, the better it is.

To help Gakrobera, find the best possible way to load minecarts, given the weights of each stone from 1 to N.

For example, with an optimal load L = 2000 kg, given four stones of 700 kg, Gakrobera will prefer to load them all in a single minecart (total score 800² = 640 000). But given four stones of 800 kg, Gakrobera will prefer to load two minecarts with two stones (total score 400² + 400² = 320 000).

Beware: the situation in the Mines of Moria has gone wild, the Dwarves push cupidity too far, the optimal load can be very high! The Balrog will soon be awaken…

Input

The input begins with an integer T (1 ≤ T ≤ 1000), the number of test cases. Then T test cases follow.

Each test case is a line of space-separated integers. The first integer L (1 ≤ L ≤ 10⁶) is the optimal load. The second integer N (1 ≤ N ≤ 10⁶) is the number of stones to be loaded. Next come N integers w₁, …, w_N (1 ≤ w_i ≤ 1000), where w_i is the weight of the stone i.

Output

For each test case, output the smallest possible total score.

Example

input
3
2000 4 700 700 700 700
2000 4 800 800 800 800
2000 10 100 200 300 400 500 600 700 800 900 1000
output
640000
320000
270000

1. Compared to the situation in the problem MORIA, the optimal load is not fixed.↩︎