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