#include <bits/stdc++.h>
using LL = long long;

const int maxN = 1e6 + 10;
int T, n, k;
int a[maxN], max[maxN][21];

std::vector<int> e[maxN];

std::set<int> allowed, banned, neg;

int main() {
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
	std::cin >> T;
	while(T--) {
		std::cin >> n >> k;

		if(k == 1) {
			LL ans = 1ll * n * (n + 1) / 2;
			std::cout << ans << "\n";
			continue;
		}

		for(int i = 1; i <= n; i++) {
			std::cin >> a[i];
			e[a[i]].emplace_back(i);
			banned.insert(i);
			neg.insert(-i);
		}

		LL ans = 0;
		banned.insert(n + 1);
		neg.insert(0);

		for(int i = 1; i <= n; i++) {
			for(auto u : e[i]) {
				banned.erase(u);
				allowed.insert(u);
				neg.erase(-u);
			}
			if(e[i].size() < k) continue;

			for(int j = 0; j <= e[i].size() - k; j++) {
				int require = e[i][j + k - 1];
				int pos = *banned.lower_bound(e[i][j]);

				if(require <= pos - 1) {
					int lpos = -(*neg.lower_bound(-e[i][j]));
					lpos = std::max(lpos, (j == 0 ? 0 : e[i][j - 1]));

					ans += 1ll * (e[i][j] - lpos) * (pos - require);
				//	std::cout << pos << " " << lpos << " " << i << " " << e[i][j] << " " << require << "\n";
				}
			}
		}

		std::cout << ans << "\n";

		for(int i = 1; i <= n; i++) {
			e[a[i]].clear();
		}

		allowed.clear();
		banned.clear();
		neg.clear();
	}
	return 0;
}