A permutation is a sequence of integers from $1$ to $N$ of length $N$ containing each number exactly once. For example $(1), (4, 3, 5, 1, 2), (3, 2, 1)$ are permutations, and $(1, 1), (4, 3, 1), (2, 3, 4)$ are not.

An array $B$ is called good if it can be converted to a permutation by applying the following operation any number of times (possibly zero):

• Choose an index $i$ of $B$ and a positive integer $x$, then set $B_i = B_i - x.$

For example, the arrays $[1, 3, 5], [1, 3, 3], [2, 2]$ are good arrays while the arrays $[1, 2, 2], [2, 4, 1, 1]$ are not good.

You are given an array $A$ containing $N$ integers. Find the number of good subarrays of $A$.

Input format

• The first line contains $T$ denoting the number of test cases. The description of $T$ test cases is as follows:
• For each test case:
  • The first line contains a single integer $N$ denoting the size of array $A$.
  • The second line contains $N$ integers $A_1, A_2, \dots, A_N$ - denoting the elements of $A$.

Output format

For each test case, print the answer in a separate line.

Constraints

$1 \le T \le 10^4 \\ 1 \leq N \leq 3\cdot 10^5\\ \\1\leq A_i \le N \\ \text {Sum of $N$ over all test cases does not exceed to }3\cdot 10^5$