Max Range Queries

You have C=100,000 cakes, numbered 1 through C. Each cake has an integer height; initially, the height of each cake is 0.

There are N operations. In each operation, you are given two integers L and R, and you should increase by 1 the height of each of the cakes L,L+1,…,R. One of these N operations should be removed and the remaining N−1 operations are then performed.

Chef wants to remove one operation in such a way that after the remaining N−1 operations are performed, the number of cakes with height exactly K is maximum possible. Since Chef is a bit busy these days, he has asked for your help. You need to find the maximum number of cakes with height exactly K that can be achieved by removing one operation.

Input

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

• The first line of each test case contains two space-separated integers N and K.

• Each of the next N lines contains two space-separated integers L and R describing one operation.

Output

For each test case, print a single line containing one integer — the maximum possible number of cakes with height K.

Constraints

Constraints

• 1≤T≤100

• 2≤N≤10^5

• 1≤K≤N

• 1≤L≤R≤105

• the sum of N over all test cases does not exceed 10^6

Example Input

1
3 2
2 6
4 9
1 4

Example Output

3

Explanation

Example case 1: Let's look at what happens after an operation is removed.

• Removing operation 1: The heights of cakes 4 through 9 increase by 1. Then, the heights of cakes 1 through 4 increase by 1. The resulting sequence of heights is [1,1,1,2,1,1,1,1,1] (for cakes 1 through 9; the other cakes have heights 0). The number of cakes with height 2 is 1.

• Removing operation 2: The resulting sequence of heights of cakes 1 through 9 is [1,2,2,2,1,1,0,0,0]. The number of cakes with height 2 is 3.

• Removing operation 3: The resulting sequence of heights of cakes 1 through 9 is [0,1,1,2,2,2,1,1,1]. The number of cakes with height 2 is 3.

The maximum number of cakes with height 2 is 3.

class Codechef {
    // Number of elements is fixed -> C = 1,00,000
    public static int removeQueryIndex(int[][] queries, int K) {
        // first creating our result if all the queries were used
        int[] cakes = new int[100_000];
        for (int[] query : queries) {
            // queries are 1 indexed
            cakes[query[0]] += 1;
            if (query[1] + 1 < 100_000)
                cakes[query[1] + 1] -= 1;
        }
        // Prefix count of number of cakes with height K+1 & K
        int[] numberOfKPlusOne = new int[100_000];
        int[] numberOfKs = new int[100_000];
        int Ks = 0;
        int sum = 0;
        for (int i = 0; i < 100_000; i++) {
            sum += cakes[i];
            cakes[i] = sum;
            if (cakes[i] == K) {
                numberOfKs[i] = 1 + (i > 0 ? numberOfKs[i - 1] : 0);
                Ks++;
            } else
                numberOfKs[i] = i > 0 ? numberOfKs[i - 1] : 0;

            if (cakes[i] == K + 1)
                numberOfKPlusOne[i] = 1 + (i > 0 ? numberOfKPlusOne[i - 1] : 0);
            else
                numberOfKPlusOne[i] = i > 0 ? numberOfKPlusOne[i - 1] : 0;
        }
        int max = Integer.MIN_VALUE;
        for (int[] query : queries) {
            // Finding the query with max number of K+1 & min number of K
            int numKPlusOnes = numberOfKPlusOne[query[1]] - (query[0] > 0 ? numberOfKPlusOne[query[0] - 1] : 0);
            int numKs = numberOfKs[query[1]] - (query[0] > 0 ? numberOfKs[query[0] - 1] : 0);
            max = Math.max(max, numKPlusOnes - numKs);
        }
        return Ks + max;

    }
}