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].
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.
For each test case, output a single integer — the sum of weights of all its \frac{n(n+1)}{2} subarrays.
Example
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 .