import java.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

/**
 * Created by witalia on 12.12.14.
 */
public class Main {
	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

//		InputReader in = new InputReader(new FileInputStream(new File("input.txt")));
//		PrintWriter out = new PrintWriter(new FileOutputStream(new File("output.txt")));

		new Solver().solve(1, in, out);

		out.close();
	}
}

class Solver {
	public static final int MAX_N = 1_000_000;
	public static final int MAX_SN = 1_000_000;
	public static final int MAX_T = 1_000;
	private long[] sum;

	public void solve(int testNumber, InputReader in, PrintWriter out) {
		System.err.print("Test #" + testNumber + " - ");

		int t = in.nextInt();
		assert t > 0 && t <= MAX_T : "T " + t + " is not in range [1, " + MAX_T + "]";

		int sumn = 0;
		for (int _t = 0; _t < t; ++_t) {
			int n = in.nextInt();
			sumn += n;
			assert n > 0 && n <= MAX_N : "N " + n + " is not in range [1, " + MAX_N + "]";
			int w = in.nextInt();
			assert w > 0 && w <= n : "W " + w + " is not in range [1, " + n + "]";
			sum = new long[n];
			for (int i = 0; i < n; i++) {
				int l = in.nextInt();
				int r = in.nextInt();
				assert l >= 0 && l <= r : "L " + l + " " + r + " is not in range [0, r]";
				assert r < n : "R " + l + " " + r + " is not in range [l, n)";
				++sum[l];
				if (r + 1 < n) {
					--sum[r + 1];
				}
			}
			for (int i = 0; i < 2; i++) {
				for (int j = 1; j < n; j++) {
					sum[j] = sum[j - 1] + sum[j];
				}
			}
			long ans = Long.MAX_VALUE;
			for (int i = 0; i + w <= n; ++i) {
				long cur = (long) w * n;
				cur -= sum[i + w - 1];
				if (i > 0) {
					cur += sum[i - 1];
				}
				ans = Math.min(ans, cur);
			}
			out.println(ans);
		}
		assert sumn > 0 && sumn <= MAX_SN : "Sum of N " + sumn + " is not in range [1, " + MAX_SN + "]";

		System.err.println("ok");
	}

	private static double round(double value, int places) {
		long factor = (long) Math.pow(10, places);
		value *= factor;
		long temp = Math.round(value);
		return (double) temp / factor;
	}
}

class InputReader {
	public BufferedReader reader;
	public StringTokenizer tokenizer;

	public InputReader(InputStream stream) {
		reader = new BufferedReader(new InputStreamReader(stream), 32768);
		tokenizer = null;
	}

	public String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public float nextFloat() { return Float.parseFloat(next()); }

	public double nextDouble() { return Double.parseDouble(next()); }
}

class Pair<K, V> {
	private K key;
	private V value;

	public K getKey() {
		return key;
	}

	public void setKey(K key) {
		this.key = key;
	}

	public V getValue() {
		return value;
	}

	public void setValue(V value) {
		this.value = value;
	}

	public Pair(K key, V value) {

		this.key = key;
		this.value = value;
	}
}