Description

Muzikant, our new tiny musician, is getting more and more talented in music thanks to your efforts in The 14th UESTC Fun Programming Contest. Today, he gets trapped in a new problem when writing his next great symphony and asks for your help. Can you help him out once again?

Let's recall how a score is composed.^[1]

1. The basic units of scores are notes.
2. A bar is made up of several notes, whose duration is $\frac1{2^k}$ of a whole bar and the sum of whose duration is equal to the duration of a bar.
3. A score is made up of several bars.

After having composed hundreds of scores, Muzikant finds it difficult to write a bar from his beautiful impromptu random melodies. He then has to settle for the second best -- to choose a consecutive notes from his melody to write a bar. More formally, he will give you a sequence of notes, which is described by an array of $N$ integers $a_1, a_2,\dots, a_N$. The duration of the $i$-th note in the sequence is $\frac1{2^{a_i}}$ of a whole bar. Your task is to find out how many ways to choose a consecutive notes from the sequence to make a bar, in other words, to find the number of intervals $[l, r]$ that notes from the $l$-th to the $r$-th form a bar.

Input

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

In each test case, the first line contains one integer $N\ (1\le N\le10^6)$, followed by one further line containing $N$ integers $a_1, a_2,\dots, a_N\ (\forall i=1,2,\dots ,N,\ 0\le a_i< N)$, as described above.

It's guaranteed that the sum of $N$ isn't greater than $10^6$.

Output

For each test case, output one line with a single integer -- the number of ways to choose a consecutive interval from the note sequence given by Muzikant.

Samples

5
1
0
4
2 2 2 2
5
1 2 2 2 1
8
1 2 3 4 5 6 7 7
10
0 1 2 3 4 5 6 6 1 1

1
1
2
1
4

Note

Here are the explanations for the example above.

• For the first, second and fourth cases, we have no other choice but use all the notes to make a bar.
• For the third case, since $\frac1{2^1}+2\times\frac1{2^2}=1$, we can choose notes in interval $[1, 3]$ or $[3, 5]$ to make a bar.
• For the fifth case, there are four ways -- $[1, 1]$, $[2, 8]$, $[3, 9]$ and $[9, 10]$.

Resources

The 22nd UESTC Programming Contest Preliminary