#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,x,y) for (int i=(x);i>=(y);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
}
typedef long long ll;
#define sz 202020

int n; ll C;
int q[sz],p[sz];

int pos[sz],pre[sz],nxt[sz];

vector<pii>aa;
ll tot;
void Swap(int x,int y) {
    tot+=abs(p[x]-p[y]);
    int nx=nxt[x],ny=nxt[y];
    nxt[x]=ny,nxt[y]=nx;
    pre[nx]=y,pre[ny]=x;
    swap(pos[x],pos[y]);
    aa.push_back({pos[x],pos[y]});
}

void work() {
    cin>>n>>C;
    ll ans=0;
    rep(i,1,n) cin>>q[i]>>p[i],ans+=abs(q[i]-p[i]);
    ans/=2;
    vector<int>V(q+1,q+n+1);
    sort(V.begin(),V.end());
    rep(i,1,n) {
        int x=lower_bound(V.begin(),V.end(),q[i])-V.begin()+1;
        int y=lower_bound(V.begin(),V.end(),p[i])-V.begin()+1;
        nxt[x]=y,pre[y]=x,pos[x]=i;
    }
    sort(p+1,p+n+1);
    drep(i,n,1) while (nxt[i]!=i) {
        // rep(j,1,n) assert(pre[nxt[j]]==j);
        if (pre[i]==i) continue;
        if (pre[pre[i]]==i) {
            Swap(i,pre[i]);
            continue;
        }
        int x=pre[i],y=nxt[i];
        if (y<pre[i]) {
            Swap(x,i);
            continue;
        }
        while (233) {
            x=pre[x],y=nxt[y];
            if (y<pre[i]) {
                Swap(pre[i],pre[y]);
                break;
            }
            if (x>pre[i]) {
                Swap(x,pre[i]);
                break;
            }
        }
    }
    rep(i,1,n) assert(nxt[i]==i);
    assert(tot==ans);
    ans+=1ll*C*aa.size();
    cout<<ans<<' '<<aa.size()<<'\n';
    for (auto [x,y]:aa) cout<<x<<' '<<y<<'\n';
    aa.clear(); tot=0;
}

int main() {
    file();
    ios::sync_with_stdio(false),cin.tie(0);
    int T; cin>>T;
    while (T--) work();
    return 0;
}