#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int a[MAXN], b[MAXN], vis[MAXN], vvis[MAXN], now;

int ans[MAXN << 1];

struct node {

    int a, b, id;

    friend bool operator < (node A, node B) {

        if(A.a + A.b == B.a + B.b) return A.id < B.id;

        else return A.a + A.b < B.a + B.b;

    }

};

node sum[MAXN];

priority_queue<node> que;

void solve(int i) {

    node tmp1 = {0, 0, 0}, tmp2 = {0, 0, 0}, tmp3 = {0, 0, 0};

    while(now >= 1 && vis[now]) now--;

    if(now >= 1) tmp1 = sum[now];

    while(!que.empty() && vvis[que.top().id]) que.pop();

    if(!que.empty()) tmp2 = que.top(), que.pop();

    while(!que.empty() && vvis[que.top().id]) que.pop();

    if(!que.empty()) tmp3 = que.top(), que.pop();

    if(tmp1.a + tmp1.b > tmp2.a + tmp2.b + tmp3.a + tmp3.b) {

        ans[i] = ans[i - 2] + tmp1.a + tmp1.b;

        vis[now] = 1; vvis[now] = 1;

        que.push(tmp2); que.push(tmp3);

    } else {

        ans[i] = ans[i - 2] + tmp2.a + tmp2.b + tmp3.a + tmp3.b;

        if(tmp2.a) {

            vis[tmp2.id] = 1;

            que.push((node){0, sum[tmp2.id].b, tmp2.id});

        } else vvis[tmp2.id] = 1;

        if(tmp3.a) {

            vis[tmp3.id] = 1;

            que.push((node){0, sum[tmp3.id].b, tmp3.id});

        } else vvis[tmp3.id] = 1;

    }

}

int main() {

    int T;

    scanf("%d", &T);

    while(T--) {

        int n;

        scanf("%d", &n);

        for(int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]), sum[i].a = a[i], sum[i].b = b[i], sum[i].id = i, vis[i] = vvis[i] = 0;

        sort(sum + 1, sum + 1 + n);

        now = n;

        while(!que.empty()) que.pop();

        ans[0] = 0;

        for(int i = 1; i <= n; i++) que.push((node){sum[i].a, 0, i});

        for(int i = 2; i <= n * 2; i += 2) solve(i);

        while(!que.empty()) que.pop();

        now = n;

        for(int i = 1; i <= n; i++) que.push((node){sum[i].a, 0, i}), vis[i] = vvis[i] = 0;

        node t1 = que.top(); que.pop();

        ans[1] = t1.a; que.push((node){0, sum[t1.id].b, t1.id}); vis[t1.id] = 1;

        for(int i = 3; i <= n * 2; i += 2) solve(i);

        for(int i = 1; i <= n * 2; i++) {

            if(i != n * 2) printf("%d ", ans[i]);

            else printf("%d\n", ans[i]);

        }

    }

    return 0;

}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 5;

ll ans;

int n, K;

int a[MAXN];

int st[MAXN][21], lg[MAXN];

int L[MAXN], R[MAXN];

int vis[MAXN];

void solve(int l, int r) {

    if(l > r) return;

    int k = lg[r - l + 1];

    int pos;

    if(a[st[l][k]] >= a[st[r - (1 << k) + 1][k]]) pos = st[l][k];

    else pos = st[r - (1 << k) + 1][k];

    if(pos - l <= r - pos) {

        for(int i = l; i <= pos; i++) {   //枚举左端点

            int rr = a[pos] - K + i - 1;  //移项之后 满足rr <= 区间右端点就是满足题意的

            rr = max(rr, pos);            //大于pos 最大值才成立

            int tr = min(R[i], r);

            if(tr >= rr) ans += 1LL * (tr - rr + 1);

        }

    } else {

        for(int i = r; i >= pos; i--) {

            int ll = K - a[pos] + i + 1;

            ll = min(ll, pos);

            int tl = max(L[i], l);

            if(tl <= ll) ans += 1LL * (ll - tl + 1);

        }

    }

    solve(l, pos - 1); solve(pos + 1, r);

}

int main() {

    lg[0] = -1;

    for(int i = 1; i <= MAXN - 2; i++) lg[i] = lg[i >> 1] + 1;

    int T;

    scanf("%d", &T);

    while(T--) {

        ans = 0;

        scanf("%d%d", &n, &K);

        for(int i = 1; i <= n; i++) scanf("%d", &a[i]), st[i][0] = i;

        for(int i = 1; i <= 20; i++)

            for(int j = 1; j <= n + 1 - (1 << i); j++) {

                if(a[st[j + (1 << (i - 1))][i - 1]] >= a[st[j][i - 1]]) st[j][i] = st[j + (1 << (i - 1))][i - 1];

                else st[j][i] = st[j][i - 1];

            }

        memset(vis, 0, sizeof(vis)); L[1] = 1; vis[a[1]] = 1;

        for(int i = 2; i <= n; i++) {

            if(vis[a[i]]) L[i] = max(L[i - 1], vis[a[i]] + 1);

            else L[i] = L[i - 1];

            vis[a[i]] = i;

        }

        memset(vis, 0, sizeof(vis)); R[n] = n; vis[a[n]] = n;

        for(int i = n - 1; i >= 1; i--) {

            if(vis[a[i]]) R[i] = min(R[i + 1], vis[a[i]] - 1);

            else R[i] = R[i + 1];

            vis[a[i]] = i;

        }

        solve(1, n);

        printf("%lld\n", ans);

    }

    return 0;

}