#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	int len=0;
	char ibuf[(1<<21)+1],*iS,*iT,out[(1<<25)+1];
	#if ONLINE_JUDGE
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
	#define gh() getchar()
	#endif
	#define reg register
	inline int read(){
		reg char ch=gh();
		reg int x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	inline void putc(char ch){
		out[len++]=ch;
	}
	template<class T>
	inline void write(T x){
		if(x<0)putc('-'),x=-x;
		if(x>9)write(x/10);
		out[len++]=x%10+48;
	}
	inline void flush(){
		fwrite(out,1,len,stdout);
		len=0;
	}
	inline char getc(){
		char ch=gh();
		while(ch<'A'||ch>'Z') ch=gh();
		return ch;
	}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::getc;
using IO::putc;
#define vi vector<int>
#define pii pair<int,int>
#define mpr make_pair
#define fir first 
#define sec second
const int N=2e5+10;
int T,n,c,p[N],q[N],v[N],vis[N];
template<class P,class Q>
class HashTable{
	static const int mod=5e5+9,L=mod+10;
	int head[L],nxt[N],siz;
	P val[N];
	Q sav[N],z;
    public:
	inline void clear(){
		for(int i=1;i<=siz;i++){
			head[val[i]%mod]=0,nxt[i]=val[i]=0;
			Q tmp=z;
			swap(sav[i],tmp);
		}
		siz=0;
	}
	inline void insert(P y){
		val[++siz]=y;
		nxt[siz]=head[y%mod];
		head[y%mod]=siz;
	}
	inline Q &operator[](const P y){
		int x=y%mod;
		for(int i=head[x];i;i=nxt[i])
			if(val[i]==y)
				return sav[i];
		insert(y);
		return sav[siz];
	}
	inline bool count(const P y){
		int x=y%mod;
		for(int i=head[x];i;i=nxt[i])
			if(val[i]==y)
				return 1;
		return 0;
	}
};
HashTable<int,int>mp;
int stk[N],top;
vector<pii>ans;
inline void add(int x,int y){
	ans.push_back(mpr(x,y));
}
inline void solve(vi vec){
	int mx=0,mxp=0;
	for(int i=0;i<vec.size();i++)
		if(v[vec[i]]>mx)
			mx=v[vec[i]],mxp=i;
	vi cir;
	for(int i=mxp,j=0;j<vec.size();i=(i+1)%vec.size(),j++)
		cir.push_back(vec[i]);
	top=0;
	stk[++top]=cir[0];
	for(int i=1;i<cir.size();i++){
		int tmp=top;
		while(top&&v[stk[top]]<v[cir[i]]) top--;
		if(top<tmp){
			add(stk[top],stk[tmp]);
			for(int j=top+1;j<tmp;j++)
				add(stk[j],stk[tmp]);
		}
		stk[++top]=cir[i];
	}
	for(int i=1;i<top;i++)
		add(stk[i],stk[top]);
}
int main(){
	//freopen("swap.in","r",stdin);
	//freopen("swap.out","w",stdout);
	T=read();
	while(T--){
		n=read(),c=read();
		ll s=0;
		mp.clear(),ans.clear();
		for(int i=1;i<=n;i++){
			p[i]=read(),q[i]=read();
			s+=abs(p[i]-q[i]);
			mp[q[i]]=i,v[i]=q[i],q[i]=i;
		}
		for(int i=1;i<=n;i++)
			p[i]=mp[p[i]],vis[i]=0;
		for(int i=1;i<=n;i++){
			if(vis[i]) continue;
			vector<int>cir;
			for(int j=i;!vis[j];j=p[j])
				cir.push_back(j),vis[j]=1;
			solve(cir);
		}
		write(s/2+1ll*ans.size()*c),putc(' '),write(ans.size()),putc('\n');
		for(auto tmp:ans)
			write(tmp.fir),putc(' '),write(tmp.sec),putc('\n');
	}
	flush();
}