You are given an array of $N$ integers and your task is to sort the array using the following operations.

In one operation you can select a sub-array of the array and sort it. The cost of performing such an operation will be the square of the length of the sub-array you are sorting.

Your task is to find the minimum cost of sorting the whole array.

Input Format:

• The first line contains a single integer $T$ representing the number of test cases. Then each test case follows.
• The first line of each test case contains one integers $N$ denoting the number of elements in the array.
• The next line of each test case contains $N$ integers of the array.

Output Format:

For each test case, print the minimum cost required to sort the whole array.

Constraints:

$1 <= T <= 5$

$3 <= N <= 10^5$

$1 <= arr[i] <= 10^9$