Fixed Points#12910

Fixed Points

1 second
256 megabytes
Hard

For an array , define its weight as the number of elements that wouldn't change after sorting. For example, the weight of the array [7, 3, 1, 10] is : after sorting it would become [1, 3, 7, 10], so the second and fourth elements would remain the same, and the other two would change.

You are given a permutation of integers from to . Find the sum of weights of all its \frac{n(n+1)}{2} subarrays.

Here subarray denotes a consecutive segment of an array. For example, array [7, 3, 1, 10] has subarrays: [7], [3], [1], [10], [7, 3], [3, 1], [1, 10], [7, 3, 1], [3, 1, 10], [7, 3, 1, 10].

Input

The first line contains a single integer (1 \le t \le 10^4)  — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer (1 \leq n \leq 2000)  — the length of the permutation.

The second line of each test case contains integers p_1, p_2, \ldots, p_n (1 \le p_i \le n, all p_i are distinct)  — elements of the permutation.

It is guaranteed that the sum of n^2 over all test cases does not exceed 4\cdot 10^6.

Output

For each test case, output a single integer  — the sum of weights of all its \frac{n(n+1)}{2} subarrays.

Examples

Example

Loading
Loading

Note

In the first test case, for each subarray, all its elements will remain fixed after sorting. So, the answer is 1\cdot 4 + 2\cdot 3 + 3\cdot 2 + 4\cdot 1 = 20, since there are subarrays with length , subarrays with length , subarrays with length , and subarray with length .