• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

Mammad owns a small woodcraft manufactory in a very humid city near the coastline. He needs to buy raw wood cubes to build customer orders. Since the transportation is a difficult procedure, he prefers to buy a certain amount of wood once a year and store them in the inventory. But as the raw wood gets cropped during the time in humid climates, he has to use some special spray to protect them which is pretty expensive. So he wants to stack them in the inventory in such a way that the total spray he needs to use becomes minimal. He wants only make one stack and for ease of finding different sizes, he does not want to put more than one piece directly on top of the other. Having the size of the cubes, calculate the minimum outer surface of the stack which he should the spray on. (The surface hidden between the woods or between the floor and the woods does not need to be sprayed)

ورودی

In the first line there will be an integer $T$ indicating the number of test cases.

$$1 \leq T \leq 100$$

Each test case begins with an integer $N$, indicating the number of cubes following $N$ lines containing an integer $d_i$ indicating the dimensions of each cube.

$$1 \leq N \leq 10^7$$ $$0 \leq d_i \leq 10^9$$

خروجی

For each test case, print an integer indicating the minimum exposed surface when the cubes are stacked in an efficient way.

مثال‌ها

ورودی نمونه ۱

2

3
5
3
5

7
10
3
1
7
3
6
9

خروجی نمونه ۱

261
1240