A known chef has prepared n dishes: the i-th dish consists of a_i grams of fish and b_i grams of meat. 

The banquet organizers estimate the balance of n dishes as follows. The balance is equal to the absolute value of the difference between the total mass of fish and the total mass of meat.

Technically, the balance equals to \left|∑_{i=1}^n a_i - ∑_{i=1}^n b_i\right|. The smaller the balance, the better.

In order to improve the balance, a taster was invited. He will eat exactly m grams of food from each dish. For each dish, the taster determines separately how much fish and how much meat he will eat. The only condition is that he should eat exactly m grams of each dish in total.

Determine how much of what type of food the taster should eat from each dish so that the value of the balance is as minimal as possible. If there are several correct answers, you may choose any of them.

Input

The first line of input data contains an integer t (1 ≤ t ≤ 10^4) — the number of the test cases.

Each test case's description is preceded by a blank line. Next comes a line that contains integers n and m (1 ≤ n ≤ 2 ⋅ 10^5; 0 ≤ m ≤ 10^6). The next n lines describe dishes, the i-th of them contains a pair of integers a_i and b_i (0 ≤ a_i, b_i ≤ 10^6) — the masses of fish and meat in the i-th dish.

It is guaranteed that it is possible to eat m grams of food from each dish. In other words, m ≤ a_i+b_i for all i from 1 to n inclusive.

The sum of all n values over all test cases in the test does not exceed 2 ⋅ 10^5.

Output

For each test case, print on the first line the minimal balance value that can be achieved by eating exactly m grams of food from each dish.

Then print n lines that describe a way to do this: the i-th line should contain two integers x_i and y_i (0 ≤ x_i ≤ a_i; 0 ≤ y_i ≤ b_i; x_i+y_i=m), where x_i is how many grams of fish taster should eat from the i-th meal and y_i is how many grams of meat.

If there are several ways to achieve a minimal balance, find any of them.

Example

Input


8

1 5
3 4

1 6
3 4

2 2
1 3
4 2

2 4
1 3
1 7

3 6
1 7
1 8
1 9

3 6
1 8
1 9
30 10

3 4
3 1
3 2
4 1

5 4
0 7
6 4
0 8
4 1
5 3


Output


0
2 3
1
3 3
0
1 1
1 1
2
1 3
0 4
3
0 6
0 6
0 6
7
1 5
1 5
6 0
0
3 1
3 1
3 1
0
0 4
2 2
0 4
3 1
1 3
for _ in range(int(input())):
    input()
    n, m = map(int, input().split())
    a = []
    b = []
    for i in range(n):
        ai, bi = map(int, input().split())
        a.append(ai)
        b.append(bi)
    suma = sum(a)
    sumb = sum(b)
    diff = suma - sumb
    ms = [m] * n
    ansa = [0] * n
    ansb = [0] * n
    for i in range(n):
        ma = m - b[i] if m > b[i] else 0
        mb = m - a[i] if m > a[i] else 0
        ansa[i] += ma
        ansb[i] += mb
        ms[i] -= ma + mb
        diff -= ma - mb
    for i in range(n):
        if diff > 0:
            m1 = ms[i] if ms[i] < diff else diff
            ansa[i] += m1
            diff -= m1
            ms[i] -= m1
        elif diff < 0:
            m2 = ms[i] if ms[i] < -diff else -diff
            ansb[i] += m2
            diff += m2
            ms[i] -= m2
        half = ms[i] // 2
        ansa[i] += half
        ansb[i] += ms[i] - half
        diff += ms[i] % 2
    print(abs(diff))
    for i in range(n):
        print(ansa[i], ansb[i])
            
        