Chef has an array A consisting of N elements. He wants to find number of pairs of non-intersecting segments [a, b] and [c, d] (1 ≤ a ≤ b < c ≤ d ≤ N) such there is no number that occurs in the subarray {Aa, Aa+1, ... , Ab} and   {Ac, Ac+1, ... , Ad} simultaneously. 
Help Chef to find this number.

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N denoting the number of elements in the array.
- The second line contains N space-separated integers A1, A2, ..., AN. 

-----Output-----
- For each test case, output a single line containing one integer - number of pairs of non-intersecting segments. 

-----Constraints-----
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 1000
- 1 ≤ Ai ≤ 109

-----Subtasks-----Subtask 1 (7 points)
- 1 ≤ N ≤ 20Subtask 2 (34 points)
- 1 ≤ N ≤ 300Subtask 3 (59 points)
- Original constraints

-----Example-----
Input:
2
3
1 2 3
4
1 2 1 2

Output:
5
4

-----Explanation-----
Example case 1.
All possible variants are correct: {[1, 1], [2, 2]}, {[1, 1], [2, 3]}, {[1, 2], [3, 3]}, {[2, 2], [3, 3]}, {[1,1], [3, 3]}.

Example case 2.
Correct segments: {[1, 1], [2, 2]}, {[1, 1], [4, 4]}, {[2, 2], [3, 3]}, {[3, 3], [4, 4]}.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "t = int(input())\n#nsum = [ z*(z+1)/2 for z in xrange(1001)]\nfor i in range (t):\n n = int(input())\n a = input().split()\n a = [ int(x) for x in a]\n if n==1:\n  print('0')\n  continue\n pos = {}\n for j in range(n):\n  if pos.get(a[j],[])==[]:\n   for k in range(j+1,n):\n    if a[j] == a[k] :\n     pos[a[j]] = pos.get(a[j],[]) + [k]\n total = 0\n for j in range(n-1):\n  ar = []\n  for k in range(j,-1,-1):\n   for x in pos.get(a[k],[]):\n    if x>j:\n     ar += [x]\n   ar.sort()\n   if len(ar) > 0:\n    total += (ar[0] - j-1)*(ar[0]-j)/2 + (n - ar[-1]-1)*(n-ar[-1])/2\n    #print ar\n    #print (ar[0] - j-1)*(ar[0]-j)/2 + (n - ar[-1]-1)*(n-ar[-1])/2\n   else:\n    total += (n-j-1)*(n-j)/2\n    #print ar\n    #print (n-j-1)*(n-j)/2\n   for x in range(len(ar[0:-1])):\n    total = total + (ar[x+1]-ar[x]-1)*(ar[x+1]-ar[x])/2\n    #print (ar[x+1]-ar[x]-1)*(ar[x+1]-ar[x])/2\n print(total)"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13813