#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define mkp make_pair
typedef long long ll;
const int N=2e5+5;

int n,C;
int p[N],q[N];
int help[N];
bool vis[N];
int lst[N],nxt[N];
vector<pii> opt;
int rid[N];
int iv[N];
void swp(int &x,int &y) {
	x^=(y^=(x^=y));
}
void work() {
	int i,j,l,r;
	int tp;
	for(i=n;i>=1;) {
		tp=iv[i];
		//cout<<i<<" "<<tp<<endl;
		if(lst[tp]==tp) { --i;continue;}
		if(lst[lst[tp]]==tp) { 
			opt.push_back(mkp(rid[tp],rid[lst[tp]]));
			lst[lst[tp]]=lst[tp],lst[tp]=tp;
			--i;
			continue;
		}
		for(l=nxt[tp],r=lst[tp];;l=nxt[l],r=lst[r]) {
		//cout<<tp<<" "<<l<<" "<<r<<" "<<i<<" "<<p[tp]<<" "<<p[l]<<" "<<p[r]<<endl;
			if(p[l]<=p[lst[tp]]) {
				//cout<<"A:"<<lst[l]<<" "<<lst[tp]<<" "<<rid[lst[l]]<<" "<<rid[lst[tp]]<<endl;
				opt.push_back(mkp(rid[lst[l]],rid[lst[tp]]));
				//swp(p[lst[l]],p[lst[tp]]);
				swp(rid[lst[tp]],rid[lst[l]]);
				//swp(q[lst[l]],q[lst[tp]]);			
				swp(nxt[lst[tp]],nxt[lst[l]]);
				swp(lst[tp],lst[l]);
				break;
			} else if(p[r]>p[lst[tp]]) {
				//cout<<"B:"<<r<<" "<<lst[tp]<<" "<<rid[r]<<" "<<rid[lst[tp]]<<endl;
				opt.push_back(mkp(rid[r],rid[lst[tp]]));
				//swp(p[r],p[lst[tp]]);
				//swp(q[r],q[lst[tp]]);
				swp(rid[r],rid[lst[tp]]);
				j=nxt[r];
				swp(nxt[r],nxt[lst[tp]]);
				swp(lst[j],lst[tp]);
				break;
			}
		}
	}
} 
void sol()
{
	int i,j;
	fill(vis,vis+1+n,0);
	scanf("%d%d",&n,&C);
	//mp.clear();
	for(i=1;i<=n;i++) {
		scanf("%d%d",&p[i],&q[i]);
		help[i]=p[i];
	}

	ll ansv=(ll)2*n*C;
	int ans=n;
	opt.clear();

	for(i=1;i<=n;i++) ansv+=abs(p[i]-q[i]),rid[i]=i;
	sort(help+1,help+1+n);
	for(i=1;i<=n;i++) {
		p[i]=lower_bound(help+1,help+1+n,p[i])-help;
		q[i]=lower_bound(help+1,help+1+n,q[i])-help;
		iv[p[i]]=i;
	}
	for(i=1;i<=n;i++) {
		if(vis[i]) continue;
		ans--,ansv-=2*C;
		for(j=i;!vis[j];j=iv[q[j]]) {
			vis[j]=1;
			lst[iv[q[j]]]=j;
			nxt[j]=iv[q[j]];
		}
	}
	work();
	printf("%lld %d\n",ansv/2,ans);
	for(pii t:opt) printf("%d %d\n",t.fi,t.se);
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t) {
		--t;
		sol();
	}
	return 0;
} 
/*
任意操作，不会合并两个环，因为这样会增加操作次数且难以减少代价
每次操作是选择两个点交换其出度，这样总会将原来的环分成两个独立的环
总操作次数仍为环长-1
于是答案有下界 1/2 * sigma(abs(p[i]-q[i])) + (n-置换环个数)*C
这要求每次选择的两个点 i,j (q[i]<q[j]) 应当满足 q[i]<=p[j]<=p[i]<=q[j]
每次选择 q 最大的点 x，一定存在点满足限制
否则这要么是自环要么根本不构成环
长度 <=2 的环容易计算，只考虑长度 >=3 的环
设连边情况为 ...->y[2]->y[1]->x->z[1]->z[2]->... 
设 y[0]=z[0]=x,若 z[i>0] > y[1],交换 y[1] 和 z[i-1]
若 z[i>1] > z[1] ，交换 z[i] 和 z[1] 即可
同时找 y[i],z[i]，一定能在不超过 len/2 次前找到合法的 y/z
复杂度即为 nlogn
每次都解决最大点所在的环即可
*/