Rounddog always has an array a1,a2,⋯,an in his right pocket, satisfying 1≤ai≤n.
A subarray is a non-empty subsegment of the original array. Rounddog defines a good subarray as a subsegment al,al+1,⋯,ar that all elements in it are different and max(al,al+1,…,ar)−(r−l+1)≤k.
Rounddog is not happy today. As his best friend, you want to find all good subarrays of a to make him happy. In this case, please calculate the total number of good subarrays of a.
Input
The input contains several test cases, and the first line contains a single integer T (1≤T≤20), the number of test cases.
The first line of each test case contains two integers n (1≤n≤300000) and k (1≤k≤300000).
The second line contains n integers, the i-th of which is ai (1≤ai≤n).
It is guaranteed that the sum of n over all test cases never exceeds 1000000.
Output
One integer for each test case, representing the number of subarrays Rounddog likes.