Given an array A of length N, count the number of good subarrays in A. A subarray is considered good if for each element that appears in the subarray, it appears a power of two number of times (i.e. 1, 2, 4, 8 and so on).

Input Format

• The first line contains T, the number of testcases.
• Then the testcases follow. For each test case,
  • The first line contains an integer N - the size of the array.
  • The next line contains N integers - the array elements.

Output Format

For each testcase, print a single line containing the answer.

Constraints

• 1 ≤ T ≤ 10^5
• 1 ≤ N ≤ 10^5
• 1 ≤ A[i] ≤ N for each 0 ≤ i < N.
• It's guaranteed that the sum of N over all testcases doesn't exceed 10 ^ 5.

Sample 0

Input

5
4
1 2 1 1
3
1 1 1
2
1 2
3
2 2 3
6
3 6 6 2 4 2

Output

9
5
3
6
21

Explanation

Let's look at the second testcase where the array is [1, 1, 1], then we can see that the good subarrays are:

1. sub(1,1)

2. sub(1,2)

3. sub(2,2)

4. sub(2,3)

5. sub(3,3)

Where sub(l,r) is the subarray that starts at l and ends at r. And so, since the number of these subarrays is 5, the answer is equal to 5.