Ali has an array of $n$ distinct numbers.

He wants to calculate the sum of F(L, R), where F(L, R) is the mex of the numbers in the subarray [L, R]  (0 <= L <= R <= n-1).

Knowing that the mex of an array is the minimum excluded number (mex(1,2) = 0, mex(0,1,2)= 3).

Can you help Ali to find the sum of F(L, R) for all subarrays?

The input consists of multiple test cases. The first line contains a single integer $t (1 \le t \le 10^4)$ --- the number of test cases.

The first line of each test case contains one integer $n (1 \le n \le 2 \cdot 10^5)$---the number of elements in the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2, \dots ,a_n (0 \le a_i \le n-1)$ the elements of the array $a$.

It's guaranteed that each value in the array $a$ appears exactly once and the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

The sum of F(L, R) for all subarrays.