#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 2e5 + 5;

class Segment {
private:
    struct Node {
        int mx, cnt, tag;
    } node[N << 2];
    int n;
public:
    void init (int _n) {
        n = _n;
    }
    void push_up (int p) {
        int ls = p << 1, rs = p << 1 | 1;
        if (node[ls].mx == node[rs].mx) {
            node[p].cnt = node[ls].cnt + node[rs].cnt;
            node[p].mx = node[ls].mx;
        } else {
            if (node[ls].mx < node[rs].mx) {
                node[p].mx = node[rs].mx;
                node[p].cnt = node[rs].cnt;
            } else {
                node[p].mx = node[ls].mx;
                node[p].cnt = node[ls].cnt;
            }
        }
    }
    void build (int s, int t, int p = 1) {
        node[p].tag = 0;
        if (s == t) {
            node[p].mx = n;
            node[p].cnt = 1;
            return;
        }
        int mid = (s + t) >> 1;
        build(s, mid, p << 1);
        build(mid + 1, t, p << 1 | 1);
        push_up(p);
    }
    void push_down (int p) {
        int ls = p << 1, rs = p << 1 | 1;
        if (node[p].tag) {
            node[ls].tag += node[p].tag;
            node[rs].tag += node[p].tag;
            node[p].tag = 0;
        }
    }
    void update (int l, int r, int v, int s, int t, int p = 1) {
        if (l <= s && t <= r) {
            node[p].mx += v;
            node[p].tag += v;
            return;
        }
        push_down(p);
        int mid = (s + t) >> 1;
        if (l <= mid) update(l, r, v, s, mid, p << 1);
        if (mid < r) update(l, r, v, mid + 1, t, p << 1 | 1);
        push_up(p);
    }
    pair<int, int> query (int l, int r, int s, int t, int p = 1) {
        if (l <= s && t <= r) return {node[p].mx, node[p].cnt};
        int mid = (s + t) >> 1;
        if (r <= mid) return query(l, r, s, mid, p << 1);
        else if (mid < l) return query(l, r, mid + 1, t, p << 1 | 1);
        else {
            auto res1 = query(l, r, s, mid, p << 1);
            auto res2 = query(l, r, mid + 1, t, p << 1 | 1);
            if (res1.first == res2.first) {
                return {res1.first, res1.second + res2.second};
            } else {
                if (res1.first > res2.first) return res1;
                return res2;
            }
        }
    }
};
Segment seg;

int n, k, tot;
map<int, int> id;
int a[N];
vector<int> pos[N];
pair<int, int> lst[N], nxt[N];
int nxta[N];

void init () {
    tot = 0;
    cin >> n >> k;
    id.clear();
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        if (!id[a[i]]) id[a[i]] = ++ tot;
        a[i] = id[a[i]];
    }
    for (int i = 1; i <= tot; i ++) {
        pos[i].clear();
    }
    for (int i = n; i >= 1; i --) {
        if (pos[a[i]].size() > 0) nxta[i] = pos[a[i]].back() - 1;
        else nxta[i] = n;
        pos[a[i]].push_back(i);
        if (pos[a[i]].size() < k) {
            nxt[i] = {-1, -1};
        } else {
            int tmp = pos[a[i]].size();
            int l = pos[a[i]][tmp - k];
            int r = tmp > k ? pos[a[i]][tmp - k - 1] - 1 : n;
            nxt[i] = {l, r};
        }
    }
    for (int i = 1; i <= n; i ++) {
        cout << a[i] << " \n"[i == n];`
    }
    for (int i = 1; i <= tot; i ++) {
        lst[i] = {-1, -1};
//      cout << i << ' ' << lst[i].first << ' ' << n << endl;
    }
    seg.init(tot);
    seg.build(1, n);
    auto [mx, cnt] = seg.query(1, n, 1, n);
    cout << "init: " << mx << ' ' << cnt << endl;
}

void solve() {
    init();
    ll ans = 0;
    for (int i = n; i >= 1; i --) {
        cout << i << " **************************\n";
        if (lst[a[i]].first != -1) {
            auto [l, r] = lst[a[i]];
            seg.update(l, r, -1, 1, n);
            cout << "del: " << l << ' ' << r << endl;
        }
        seg.update(1, nxta[i], -1, 1, n);
        cout << "del: " << 1 << ' ' << nxta[i] << endl;
        lst[a[i]] = nxt[i];
        auto [l, r] = nxt[i];
        cout << i << " [" << l << ' ' << r << "]" << endl;
        if (i > 1) {
            seg.update(1, i - 1, 1, 1, n);
            cout << "add: " << 1 << ' ' << i - 1 << endl;
        }
        if (l > 0) {
            seg.update(l, r, 1, 1, n);
            cout << "add: " << l << ' ' << r << endl;
            auto res = seg.query(l, r, 1, n);
            if (res.first == tot) ans += res.second;
            cout << res.first << ' ' << res.second << endl;
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}