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\)