Farmer John 有一个数组 $$$a$$$,其中包含 $$$n$$$ 正整数和一个整数 $$$k$$$。
令 $$$a[l, r]$$$ 为 $$$a$$$ 的子数组$$$^{\text{*}}$$$。他执行以下过程来独立确定子数组 $$$a[l, r]$$$ 是否很棒:
- 最初,FJ 有 $$$k$$$ 空多重集,编号从 $$$1$$$ 到 $$$k$$$。
- 然后,对于 $$$a$$$ 中的每个元素 $$$a_i$$$ ($$$1 \leq i \leq n$$$):
- 如果 $$$l\leq i\leq r$$$ (即 $$$a_i$$$ 在子数组 $$$a[l, r]$$$ 中),他将 $$$a_i$$$ 放入多重集 $$$1$$$ 中,
- 否则,他将 $$$a_i$$$ 放入他想要的任何多重集中 (可能是多重集 $$$1$$$).
- 子数组 $$$a[l, r]$$$ 非常棒,如果有某种方法可以让他放置元素,使得对于每个值 $$$v$$$,所有多重集都包含相同数量的值为 $$$v$$$ 的元素。换句话说,他想让所有多重集包含完全相同的元素(忽略顺序)。
输出awesome子数组的数量。
$$$^{\text{*}}$$$对于大小为 $$$n$$$ 的数组 $$$a$$$ 和整数 $$$1\leq l\leq r\leq n$$$,子数组 $$$a[l, r]$$$ 表示按顺序由元素 $$$a_l、\ldots、a_r$$$ 组成的数组。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq k \le n \leq 2 \cdot 10^5$$$)。
以下行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在新行中输出一个整数:awesome 子数组的数量。
示例
输入复制
43 21 1 14 21 2 1 28 23 3 3 3 2 2 2 26 31 1 1 1 1 1
输出复制
0 7 18 11
注意
测试用例1: $$$n=3$$$,$$$a=[1,1,1]$$$。
对于 $$$k=2$$$,您无法在两个多重集中以相同数量的 $$$1$$$ 结束,因此子数组不起作用。
测试用例2: $$$n=4$$$,$$$a=[1,2,1,2]$$$。
对于 $$$k=2$$$,最终状态必须为每个多重集恰好提供一个 $$$1$$$ 和一个 $$$2$$$。因此,一个有效的子数组可以包含 最多 1 个 $$$1$$$ 和 最多 1 个 $$$2$$$.