In the Mines of Moria, the job of Gakrobera Silverborn the dwarf is 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.

Each stone has a weight between 1 kg and 1000 kg, which we assume to be an integer. The optimal load of a mine cart is 2000 kg. The score of a minecart loaded with W kg of stones is (W − 2000)². After all stones have been loaded in minecarts, the total score is the sum of the score of each minecart. 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, 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).

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 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
4 700 700 700 700
4 800 800 800 800
10 100 200 300 400 500 600 700 800 900 1000
output
640000
320000
270000