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 = 'z = []\nfor i in range(1001):\n z.append(i * (i-1) / 2)\nfor t in range(int(input())):\n n = int(input())\n a = list(map(int, input().split())) \n d = {}\n for i in range(n):\n  d[a[i]] = []\n for i in range(n):\n  d[a[i]].append(i) \n ans = 0\n for i in range(n):\n  temp = []\n  pos = []\n  for j in range(i,n):\n   if (a[j] not in temp):\n    temp.append(a[j])\n    l1 = pos\n    l2 = d[a[j]]\n    pos = []\n    i1 = 0\n    i2 = 0\n    len1 = len(l1)\n    len2 = len(l2)\n    while (i1<len1 and i2<len2):\n     if (l1[i1] < l2[i2]):\n      pos.append(l1[i1])\n      i1 += 1\n     else:\n      pos.append(l2[i2])\n      i2 += 1\n    while (i1<len1):\n     pos.append(l1[i1])\n     i1 += 1\n    while (i2<len2):\n     pos.append(l2[i2])\n     i2 += 1\n     \n    if (pos[-1] != (n-1)):\n     f = pos + [n]\n    else:\n     f = pos\n   curr = 0\n   for p in range(1,len(f)):\n    if (f[p] > j):\n     xxx = (f[p] - f[p-1])\n     curr += z[xxx]\n   ans += curr\n print(ans)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 46979