T3 统计

题目信息

时间限制: 1s

空间限制: 256M

输入文件: st.in

输出文件: st.out

题目描述

给定一个数列 $A$，数列的元素取值范围为 $[1,m]$。

请计算有多少个非空子区间满足以下条件：该区间内每个元素的出现次数都相同（没有出现的元素视为出现 $0$ 次）。

例如，当 $m=3$ 时，$[1,2,3]$ 和 $[1,1,3,2,3,2]$ 是满足条件的区间，而 $[1,2,2,3]$ 和 $[1,1,3,3]$ 不满足条件。

请计算数列 $A$ 的满足条件的非空子区间数量。

输入格式

包含多组测试数据，第一行一个正整数 $T$ 代表数据组数。

每组数据两行，第一行两个整数 $n, m$，代表序列长度和元素值域。

第二行 $n$ 个整数，代表该序列，保证序列中的元素在 $[1, m]$ 之间。

输出格式

$T$ 行，每行一个整数，代表对应组数数据的序列的满足条件的非空子区间个数。

样例

样例输入 1

1
6 3
1 2 3 1 2 3

样例输出 1

5

样例解释 1

有 $[1, 3], [2, 4], [3, 5], [4, 6], [1, 6]$ 共 $5$ 个。

样例输入 2

1
10 4
1 1 2 4 3 2 4 3 2 1

样例输出 2

3

样例解释 2

有 $[2, 5], [1, 8], [7, 10]$ 共 $3$ 个。

更多样例

见附加文件。

数据范围与提示

对于 $100 \%$ 的数据, $1 \leq T \leq 5,1 \leq n \leq 10^6, 1 \leq m \leq n$。