#include <algorithm>
#include <deque>
#include <format>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <utility>
using LL = long long;
template<typename T>
void upd_max(T &a, T b) { if (a < b) a = b; }
template<typename T>
void upd_min(T &a, T b) { if (a > b) a = b; }
constexpr int N = 3E5;
int a[N];
int next[N + 1];
struct info
{
    int i, j;
};
void solve()
{
    int n, k; std::cin >> n >> k;
    ++k;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    int max_r = n;
    std::fill_n(next + 1, n, n);
    std::deque<int> q;
    std::set<info, decltype([](const info &u, const info &v) {
        return a[u.i] - u.j < a[v.i] - v.j;
    })> s0;
    std::set<info, decltype([](const info &u, const info &v) {
        return a[u.i] - u.i < a[v.i] - v.i;
    })> s1;
    LL sum0 = 0;
    LL sum1 = 0;
    LL ans = 0;
    for (int l = n; ~--l; )
    {
        upd_min(max_r, next[a[l]]);
        next[a[l]] = l;
        auto erase = [&](int i, int j) {
            sum0 -= a[i] - j;
            s1.erase({i, j});
        };
        auto emplace = [&](int i, int j) {
            s1.emplace(i, j);
            sum0 += a[i] - j;
        };
        auto erase_ = [&](auto iter) {
            sum0 -= a[iter->i] - iter->j;
            s1.erase(iter);
        };
        auto pop_front = [&]() {
            int i = q.front();
            q.pop_front();
            if (!q.empty())
            {
                int j = q.front();
                if (k - l <= a[i] - j)
                    s0.erase({i, j});
                else if (k - l <= a[i] - i)
                    erase(i, j);
                else
                    sum1 -= j - i;
            }
        };
        auto push_front = [&](int i) {
            if (!q.empty())
            {
                int j = q.front();
                if (k - l <= a[i] - j)
                    s0.emplace(i, j);
                else if (k - l <= a[i] - i)
                    emplace(i, j);
                else
                    sum1 += j - i;
            }
            q.push_front(i);
        };
        auto pop_back = [&]() {
            int j = q.back();
            q.pop_back();
            if (!q.empty())
            {
                int i = q.back();
                if (k - l <= a[i] - j)
                    s0.erase({i, j});
                else if (k - l <= a[i] - i)
                    erase(i, j);
                else
                    sum1 -= j - i;
            }
        };
        while (!q.empty() && a[l] >= a[q.front()])
            pop_front();
        push_front(l);
        while (q.back() >= max_r)
            pop_back();
        while (!s0.empty() && a[s0.begin()->i] - s0.begin()->j < k - l)
        {
            auto [i, j] = *s0.begin();
            emplace(i, j);
            s0.erase(s0.begin());
        }
        while (!s1.empty() && a[s1.begin()->i] - s1.begin()->i < k - l)
        {
            sum1 += s1.begin()->j - s1.begin()->i;
            erase_(s1.begin());
        }
        int i = q.back();
        ans += static_cast<LL>(s1.size()) * (k - l) - sum0 + sum1 + (k - l <= a[i] - max_r ? 0 : k - l <= a[i] - i ? k - l - (a[i] - max_r) : max_r - i);
    }
    std::cout << ans << "\n";
}
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
    int T; std::cin >> T;
    while (T--) solve();
}