E. Splittime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputFarmer John has an array $$$a$$$ containing $$$n$$$ positive integers and an integer $$$k$$$. Let $$$a[l, r]$$$ be a subarray$$$^{\text{∗}}$$$ of $$$a$$$. He performs the following procedure to independently determine if subarray $$$a[l, r]$$$ is awesome: Initially, FJ has $$$k$$$ empty multisets, numbered from $$$1$$$ to $$$k$$$. Then, for each element $$$a_i$$$ ($$$1 \leq i \leq n$$$) in $$$a$$$: If $$$l\leq i\leq r$$$ (that is, $$$a_i$$$ is in the subarray $$$a[l, r]$$$), he places $$$a_i$$$ in multiset $$$1$$$, Otherwise, he places $$$a_i$$$ into any multiset he wants (which may be multiset $$$1$$$). Subarray $$$a[l, r]$$$ is awesome if there is some way for him to place elements such that, for every value $$$v$$$, all multisets contain the same number of elements with value $$$v$$$. In other words, he wants to make all multisets contain the exact same elements (ignoring ordering). Output the number of awesome subarrays. $$$^{\text{∗}}$$$For array $$$a$$$ of size $$$n$$$ and integers $$$1\leq l\leq r\leq n$$$, the subarray $$$a[l, r]$$$ denotes the array consisting of the elements $$$a_l, \ldots, a_r$$$, in order.InputThe first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq k \le n \leq 2 \cdot 10^5$$$).The following line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.OutputFor each testcase, output one integer on a new line: the number of awesome subarrays.ExampleInput43 21 1 14 21 2 1 28 23 3 3 3 2 2 2 26 31 1 1 1 1 1Output0
7
18
11
NoteTest case 1: $$$n=3$$$, $$$a=[1,1,1]$$$.For $$$k=2$$$, you cannot finish with the same number of $$$1$$$'s in both multisets, so no subarray works. Test case 2: $$$n=4$$$, $$$a=[1,2,1,2]$$$. For $$$k=2$$$, the final state must give each multiset exactly one $$$1$$$ and one $$$2$$$. Thus a valid subarray can contain at most one $$$1$$$ and at most one $$$2$$$.