#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 2e5 + 5;
int n, C;
int p[N], q[N], pos[N], pool[N];
int nxt[N], pre[N];
vector<array<int, 2>> res;
int sum;
void Swap(int u, int v) {
	assert(u != v);
	int nu = nxt[u], nv = nxt[v];
	swap(nxt[u], nxt[v]);
	swap(pre[nu], pre[nv]);
	sum += abs(pool[u] - pool[v]) + C;
	res.push_back({pos[u], pos[v]});
	swap(pos[u], pos[v]);
	swap(p[pos[u]], p[pos[v]]);
}
void solve() {
	cin >> n >> C;
	for (int i = 1; i <= n; i++) {
		cin >> p[i] >> q[i];
		pool[i] = p[i];
	}
	sort(pool + 1, pool + n + 1);
	for (int i = 1; i <= n; i++) {
		int u = lower_bound(pool + 1, pool + n + 1, p[i]) - pool;
		int v = lower_bound(pool + 1, pool + n + 1, q[i]) - pool;
		nxt[u] = v;
		pre[v] = u;
		pos[u] = i;
	}
	for (int v = n; v >= 1; v--) {
		while (nxt[v] != v) {
			int x = pre[v], y = nxt[v];
			if (x >= y) {
				Swap(x, v);
				continue;
			}
			for (int y1 = y, x1 = x; ; y1 = nxt[y1], x1 = pre[x1]) {
				int y2 = nxt[y1], x2 = pre[x1];
				if (y2 <= x) {
					Swap(y1, x);
					break;
				}
				if (x2 >= x) {
					Swap(x2, x);
					break;
				}
			}
		}
	}
	cout << sum << " " << res.size() << "\n";
	for (auto [i, j] : res) {
		cout << i << " " << j << "\n";
	}
	for (int i = 1; i <= n; i++) {
		assert(p[i] == q[i]);
	}
}
void clear() {
	for (int i = 1; i <= n; i++) {
		p[i] = q[i] = pos[i] = pool[i] = nxt[i] = pre[i] = 0;
	}
	res.clear();
	sum = 0;
}
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int T;
	cin >> T;
	while (T--) {
		solve();
		clear();
	}
	return 0;
}