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]}.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
t = int(input())
for q in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	dic = {}
	dic2 = {}
	for i in range(n):
		dic2[x[i]] = 1
	if len(dic2) == n:
		n += 2
		print(n * (n - 1) * (n - 2) * (n - 3) / 24)
		continue
	counter = 0
	for i in range(n - 1):
		if x[i] in dic:
			dic[x[i]] += 1
		else:
			dic[x[i]] = 1
		for j in range(i, n - 1):
			if x[j] in dic:
				dic[x[j]] += 1
			else:
				dic[x[j]] = 1
			for p in range(j + 1, n):
				if x[p] in dic:
					continue
				for q in range(p, n):
					if x[q] in dic:
						break
					counter += 1
		dic.clear()
	print(counter)


def func():
	count = 0
	for i in range(N - 1):
		for group_size in range(1, N - i):
			I = set(A[i:i + group_size])
			m = 0
			for j in range(i + group_size, N):
				if A[j] not in I:
					m += 1
				else:
					count += m * (m + 1) / 2
					m = 0
			count += m * (m + 1) / 2
	print(count)
T = int(input())
for t in range(T):
	N = int(input())
	A = input().split(' ')
	func()


def repeats(A, x):
	for i in range(N):
		if x == A[i]:
			return i
	return -1

def assign_indices(A, newA):
	for i in range(N):
		x = repeats(A, A[i])
		if x == -1:
			newA[i] = i
		else:
			newA[i] = x
T = int(input())
for t in range(T):
	N = int(input())
	A = input().split(' ')
	indices = [0 for x in range(1005)]
	for i in range(N):
		A[i] = int(A[i])
	assign_indices(A, indices)
	total = 0
	taken = []
	for i in range(N - 1):
		taken = [0 for x in range(1005)]
		for j in range(i, N):
			before = 0
			taken[indices[j]] += 1
			for k in range(j + 1, N):
				if taken[indices[k]] == 0:
					total = total + (k - j) - before
				else:
					before = k - j
	print(total)


t = int(input())
for q in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	dic = {}
	counter = 0
	for i in range(n - 1):
		if x[i] in dic:
			dic[x[i]] += 1
		else:
			dic[x[i]] = 1
		for j in range(i, n - 1):
			if x[j] in dic:
				dic[x[j]] += 1
			else:
				dic[x[j]] = 1
			for p in range(j + 1, n):
				if x[p] in dic:
					continue
				for q in range(p, n):
					if x[q] in dic:
						break
					counter += 1
		dic.clear()
	print(counter)


def func():
	count = 0
	N = len(A)
	for i in range(N - 1):
		for group_size in range(1, N - i):
			m = 0
			new_element = A[i + group_size - 1]
			for j in range(i + group_size, N):
				if group_size == 1:
					if A[j] != A[i]:
						m += 1
						marker[j] = 0
					else:
						marker[j] = 1
						count += m * (m + 1) / 2
						m = 0
				elif marker[j] == 0 and A[j] != new_element:
					m += 1
				else:
					marker[j] = 1
					count += m * (m + 1) / 2
					m = 0
			count += m * (m + 1) / 2
	print(count)
T = int(input())
marker = [0 for h in range(1005)]
for t in range(T):
	N = int(input())
	A = input().split(' ')
	func()


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[a[i]] = []
	for i in range(n):
		d[a[i]].append(i)
	ans = 0
	for i in range(n):
		temp = []
		pos = []
		for j in range(i, n):
			f = []
			if a[j] not in temp:
				curr = 0
				temp.append(a[j])
				pos += d[a[j]]
				pos.sort()
				if pos[-1] != n - 1:
					f = pos + [n]
				else:
					f = pos
			for p in range(1, len(f)):
				if f[p] > j:
					curr += (f[p] - f[p - 1] - 1) * (f[p] - f[p - 1]) / 2
			ans += curr
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	a = [int(x) for x in a]
	if n == 1:
		print('0')
		continue
	pos = {}
	for j in range(n):
		if pos.get(a[j], []) == []:
			for k in range(j + 1, n):
				if a[j] == a[k]:
					pos[a[j]] = pos.get(a[j], []) + [k]
	total = 0
	for j in range(n - 1):
		ar = []
		for k in range(j, -1, -1):
			for x in pos.get(a[k], []):
				if x > j:
					ar += [x]
			ar.sort()
			if len(ar) > 0:
				total += (ar[0] - j - 1) * (ar[0] - j) / 2 + (n - ar[-1] - 1) * (n - ar[-1]) / 2
			else:
				total += (n - j - 1) * (n - j) / 2
			for x in range(len(ar[0:-1])):
				total = total + (ar[x + 1] - ar[x] - 1) * (ar[x + 1] - ar[x]) / 2
	print(total)


for _ in range(eval(input())):
	n = eval(input())
	l = list(map(int, input().split()))
	c = 0
	s = []
	for i in range(n):
		for j in range(i, n):
			s += [set(l[i:j + 1])]
	for i in range(len(s)):
		for j in range(i + 1, len(s)):
			c += len(s[i] & s[j]) == 0
	print(c)


for _ in range(eval(input())):
	n = eval(input())
	l = list(map(int, input().split()))
	c = 0
	for i in range(n):
		for j in range(n):
			for k in range(n):
				for m in range(n):
					a = set(l[i:j + 1])
					b = set(l[k:m + 1])
					if len(a) and len(b) and (len(a & b) == 0):
						c += 1
	print(c / 2)


t = eval(input())
while t > 0:
	n = eval(input())
	ar = list(map(int, input().split()))
	c = 0
	for i in range(0, n):
		for j in range(i, n):
			for k in range(j + 1, n):
				for l in range(k, n):
					res = []
					res = list(set(ar[i:j + 1]).intersection(set(ar[k:l + 1])))
					if len(res) == 0:
						c += 1
	print(c)
	t -= 1


z = []
for i in range(1001):
	z.append(i * (i - 1) / 2)
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[a[i]] = []
	for i in range(n):
		d[a[i]].append(i)
	ans = 0
	for i in range(n):
		temp = []
		pos = []
		for j in range(i, n):
			if a[j] not in temp:
				temp.append(a[j])
				l1 = pos
				l2 = d[a[j]]
				pos = []
				i1 = 0
				i2 = 0
				len1 = len(l1)
				len2 = len(l2)
				while i1 < len1 and i2 < len2:
					if l1[i1] < l2[i2]:
						pos.append(l1[i1])
						i1 += 1
					else:
						pos.append(l2[i2])
						i2 += 1
				while i1 < len1:
					pos.append(l1[i1])
					i1 += 1
				while i2 < len2:
					pos.append(l2[i2])
					i2 += 1
				if pos[-1] != n - 1:
					f = pos + [n]
				else:
					f = pos
			curr = 0
			for p in range(1, len(f)):
				if f[p] > j:
					xxx = f[p] - f[p - 1]
					curr += z[xxx]
			ans += curr
	print(ans)