E. Đếm số đoạn con
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Cho một dãy số nguyên $$$a$$$ gồm $$$n$$$ phần tử. Một đoạn con (subarray) là một dãy liên tiếp không rỗng các phần tử của mảng, và đoạn con được gọi là tốt nếu trong nó có chính xác k giá trị phân biệt.

Nhiệm vụ của bạn là đếm xem có bao nhiêu đoạn con tốt của mảng được cho.

Input

Dòng đầu tiên chứa một số nguyên $$$t$$$ ($$$1 \leq t \leq 10^{4}$$$) — số lượng truy vấn. Với mỗi truy vấn:

  • Dòng đầu chứa hai số nguyên $$$n$$$ và $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^{5}$$$).
  • Dòng thứ hai chứa $$$n$$$ số nguyên $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$1 \leq a_{i} \leq 10^{9}$$$).

Dữ liệu vào bảo đảm tổng $$$n$$$ trong mọi testcase không vượt quá $$$2 \cdot 10^5$$$.

Output

Đối với mỗi truy vấn, in ra một dòng duy nhất — số đoạn con chứa chính xác $$$k$$$ giá trị phân biệt.

Example
Input
3
1 1
10
3 1
3 1 8
16 1
8 1 5 8 8 7 4 9 7 10 10 7 5 8 5 5
Output
1
3
19