题目描述

给定数组 $a$ 和整数 $k$。对每个子数组 $a[l,r]$，其中的元素必须放入第 1 个多重集合，其余元素可任意放入 $k$ 个多重集合。若能使最终 $k$ 个多重集合完全相同，则该子数组是好的。求好子数组个数。

输入格式

第一行包含整数 $t$。每组数据给出 $n,k$，随后一行给出数组 $a$。

输出格式

对每组数据输出好子数组数量。

样例

4
3 2
1 1 1
4 2
1 2 1 2
8 2
3 3 3 3 2 2 2 2
6 3
1 1 1 1 1 1

0
7
18
11

说明

若某个值在整个数组中的出现次数不能被 $k$ 整除，则没有任何子数组可行。

数据范围

本题来自 Codeforces Round 1050 (Div. 4)，原题编号 CF2148E，英文题名 Split。