题目描述

可怜有一个长度为 $n$ 的正整数序列 $A_i$，其中相同的正整数代表着相同的颜色。
现在可怜觉得这个序列太长了，于是她决定选择一些颜色把这些颜色的所有位置都删去。
删除颜色 $i$ 可以定义为把所有满足 $A_j = i$ 的位置 $j$ 都从序列中删去。
然而有些时候删去之后，整个序列变成了好几段，可怜不喜欢这样，于是她想要知道有多少种删去颜色的方案使得最后剩下来的序列非空且连续。
例如颜色序列 $[1, 2, 3, 4, 5]$，删除颜色 $3$ 后序列变成了 $[1, 2]$ 和 $[4, 5]$ 两段，不满足条件。
而删除颜色 $1$ 后序列变成了 $[2, 3, 4, 5]$，满足条件。
两个方案不同当且仅当至少存在一个颜色 $i$ 只在其中一个方案中被删去。

输入格式

第一行输入一个整数 $T$ 表示数据组数。
每组数据第一行输入一个整数 $n$ 表示数列长度。
第二行输入 $n$ 个整数描述颜色序列。

输出格式

对于每组数据输出一个整数表示答案。

样例

input

1
5
1 3 2 4 3

output

6

满足条件的删颜色方案有 $[1],[1, 3],[1, 2, 3],[1, 3, 4],[2, 3, 4],\varnothing$。

数据范围与提示

对于 $20\%$ 的数据，保证 $1 \leq ∑n \leq 20$。
对于 $40\%$ 的数据，保证 $1 \leq ∑n \leq 500$。
对于 $60\%$ 的数据，保证 $1 \leq ∑n \leq 10^4$。
对于 $100\%$ 的数据，保证 $1 \leq T, ∑n \leq 3 \times 10^5 , 1 \leq A_i \leq n$。