Description

You are given an integer sequence of size $n$.

A non-empty contiguous subsequence of $a$ is called beautiful if and only if every element appearing in it occurs the same number of times.

Your task is to compute the number of beautiful contiguous subsequences. The same beautiful subsequence appearing at different positions is counted multiple times.

Input Format

The first line contains a single integer $t$ — the number of test cases.

For each test case, the first line contains an integer $n$.

The second line contains $n$ integers $a_1,a_2,\dots,a_n$.

Output Format

For each test case, print a single integer — the number of beautiful contiguous subsequences in that test case.

5
9
1 1 1 2 2 2 3 3 3
4
1 1 2 2
5
1 1 2 2 1
10
1 2 2 1 1 2 3 2 3 3
12
1 1 2 3 3 2 1 2 3 3 2 1

25
8
11
26
34

Hint

Sample Explanation

In the third example, the intervals representing all beautiful subsequences are:

• $[1,1]$
• $[1,2]$
• $[1,4]$
• $[2,2]$
• $[2,3]$
• $[2,5]$
• $[3,3]$
• $[3,4]$
• $[4,4]$
• $[4,5]$
• $[5,5]$

Data Range

The problem uses subtask dependencies: failing a prerequisite subtask will result in a score of zero for any subtask.

It is guaranteed that for all testcases, $T\ge 1,1\le n,\sum n\le 10^6,1\le a_i\le n$。