#include<bits/stdc++.h>
using ll = long long;
const int maxn = 2e5 + 10;
int p[maxn], q[maxn], idp[maxn], hs[maxn];
int nxt[maxn], pre[maxn];
bool vis[maxn];
inline void Main() {
   int n, C;
   scanf("%d%d", &n, &C);
   for (int i = 1; i <= n; i++)
      scanf("%d%d", &p[i], &q[i]), hs[i] = p[i];
   std::sort(hs + 1, hs + n + 1);
   for (int i = 1; i <= n; i++)
      p[i] = std::lower_bound(hs + 1, hs + n + 1, p[i]) - hs;
   for (int i = 1; i <= n; i++)
      q[i] = std::lower_bound(hs + 1, hs + n + 1, q[i]) - hs;
   for (int i = 1; i <= n; i++)
      idp[p[i]] = i, nxt[p[i]] = q[i];
   for (int i = 1; i <= n; i++)
      pre[nxt[i]] = i;
   ll ans = 0;
   std::vector<std::pair<int, int> > sp;
   auto Swap = [&](int x, int y) {
      ans += abs(hs[x] - hs[y]) + C;
      sp.emplace_back(idp[x], idp[y]);
      std::swap(idp[x], idp[y]);
      std::swap(nxt[x], nxt[y]), std::swap(pre[nxt[x]], pre[nxt[y]]);
   };
   memset(vis, 0, sizeof(bool) * (n + 1));
   for (int _ = 1; _ <= n; _++) {
      if (vis[_]) continue;
      int mx = 0;
      for (int u = _; ! vis[u]; u = nxt[u])
         mx = std::max(mx, u), vis[u] = 1;
      std::vector<int> P;
      P.push_back(mx);
      while (true) {
         int now = pre[P.back()];
         if (now == mx) {
            for (int i = 1; i < P.size(); i++)
               Swap(P[i - 1], P[i]);
            break;
         }
         std::vector<int> del;
         while (! P.empty() && P.back() < now)
            del.push_back(P.back()), P.pop_back();
         if (del.size()) {
            Swap(now, del.back());
            for (int i = del.size() - 1; i; i--)
               Swap(del[i], del[i - 1]);
         }
         P.push_back(now);
      }
   }
   printf("%lld %zu\n", ans, sp.size());
   for (auto _ : sp)
      printf("%d %d\n", _.first, _.second);
}
int main() {
   int T;
   scanf("%d", &T);
   while (T--) Main();
   return 0;
}