Story

Cherry, a male bee ninja living in Manhattan, enjoys flying drones as a hobby. Today, too, Cherry is flying his drone toward all sorts of places.

So that the battery does not run out, let's give some advice to Cherry, who is higher up than the sky.

Problem Statement

Define the square region $R$ on the $xy$ plane by $R:=\{(x,y) \mid 0 \leq x \leq L, 0 \leq y \leq L\}$. A drone flies within this $R$.

There are $N$ checkpoints in $R$, and the $i~(1 \leq i \leq N)$-th checkpoint $P_i$ is located at the coordinates $(X_i, Y_i)$.

Here, for $2$ points $S=(x,y), S'=(x', y')$ on the $xy$ plane, the cost $\operatorname{cost}(S,S')$ required for the drone to move from $S$ to $S'$ is $$\operatorname{cost}(S,S')=\lvert x-x' \rvert+\lvert y-y' \rvert $$

Give one example of a sequence $A=(A_1, A_2, \dots, A_M)$ of points in $R$ that satisfies the following.

• $1 \leq M \leq 2N$.
• Both the $x$ coordinate and the $y$ coordinate of $A_j$ are integers $\quad (1 \leq j \leq M)$.
• $A_j \in R \quad (j=1,2, \dots, M)$.
• $P_i$ appears at least $1$ time among $A_1, A_2, \dots, A_M$ $\quad (1 \leq i \leq N)$.
• When the drone moves in the order $A_1 \to A_2 \to \dots \to A_{M-1} \to A_M \to A_1$, the total cost is at most $1000 L$. That is, $$\sum_{j=1}^{M-1} \operatorname{cost} (A_j, A_{j+1})+\operatorname{cost}(A_M, A_1) \leq 1000L$$ holds.

It can be proved that, under the constraints of this problem, a valid $A$ exists.

Solve $T$ test cases.

Constraints

• $1 \leq T \leq 10^5$.
• Constraints for each test case.
• $2 \leq N \leq 2 \times 10^5$.
• $1 \leq L \leq 10^9$
• $0 \leq X_i \leq L, 0 \leq Y_i \leq L \quad (1 \leq i \leq N)$.
• $i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j) \quad (1 \leq i \leq N, 1 \leq j \leq N)$.
• Constraints for the test file.
  • The sum of $N$ over the $T$ test cases is at most $2 \times 10^5$.
• All inputs are integers.

Input

$T$
${\rm Testcase}_1$
${\rm Testcase}_2$
$\vdots$
${\rm Testcase}_T$

$N$ $L$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

Output

For each test case, letting $(x_j, y_j)$ be the coordinates of $A_j$ in your answer $A=(A_1,A_2, \dots, A_M)$, output in the following format.

$M$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_M$ $y_M$

Sample

2
4 6
0 1
4 2
5 3
3 1
3 1000000000
0 0
1000000000 0
1000000000 1000000000

7
3 5
0 1
2 6
5 3
3 1
4 2
1 4
5
0 0
0 1000000000
1000000000 1000000000
1000000000 0
1000000000 1000000000