There is a ring of numbers consisting of  to  sequentially. For every number ,  and  are adjacent to each other. Particularly,  and  are adjacent. We use  to describe an interval on the ring. Formally, if , then the interval  is equivalent to the set . Otherwise, the interval  is equivalent to .

Yukikaze has  non-intersecting intervals. She wants you to construct a set of intervals such that the intersection of them is the union of the  intervals that Yukikaze has. The intersection of the intervals is the set of integers that the intervals have in common.

输入描述:

The first line of the input contains a single integer , denoting the number of test cases.

The first line of each test case contains two integers  and , denoting that the ring consists of numbers from  to .

Each of the next  lines contains two integers , denoting an interval Yukikaze has. It's guaranteed that the  intervals won't intersect with each other.

输出描述:

For each test case, if the answer doesn't exist, output  in a line. Otherwise, output an integer  indicating the number of intervals you construct in a line. Then output the  intervals in  lines. The number of intervals you used should never be less than one or greater than . 

If there are multiple solutions, print any. Don't print any extra spaces at the end of each line.

2
3 1
2 2
4 2
1 1
3 3

1
2 2
2
3 1
1 3