#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void solve(){
   int n,C;cin>>n>>C;
   vector<pair<int,int>>opt;
   vector<int>p(n),q(n);
   map<int,int>ip,iq;
   i64 ans=0;
   for(int i=0;i<n;i++){
      scanf("%d%d",&p[i],&q[i]);
      ip[p[i]]=i,iq[q[i]]=i;
   }
   auto swaper=[&](int x,int y){
      x=ip[x],y=ip[y],swap(ip[p[x]],ip[p[y]]),swap(p[x],p[y]),
      ans+=C+abs(p[x]-p[y]),opt.emplace_back(x+1,y+1);
   };
   auto pre=[&](int x){return p[iq[x]];};
   auto nex=[&](int x){return q[ip[x]];};
   auto sortcyc_=[&](int lst){
      for(int u;(u=pre(lst))!=lst;swaper(u,lst),lst=u);
   };
   auto sortcyc=[&](int x){
      int mx=x;
      for(int i=nex(x);i!=x;i=nex(i))mx=max(mx,i);
      int p=mx;
      for(int v;(v=pre(p))!=mx;p=v)if(v>p){
         for(;v>nex(p);p=nex(p));
         swaper(v,p),sortcyc_(p);
      }
      sortcyc_(mx);
   };
   for(i64 x:p)if(pre(x)!=x)sortcyc(x);
   printf("%lld %d\n",ans,(int)opt.size());
   for(auto[x,y]:opt)printf("%d %d\n",x,y);
}
int main(){
   int T;for(cin>>T;T--;)solve();
   return 0;
}