310325: CF1816A. Ian Visits Mary

A. Ian Visits Marytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Ian and Mary are frogs living on lattice points of the Cartesian coordinate plane, with Ian living on $(0,0)$ and Mary living on $(a,b)$.

Ian would like to visit Mary by jumping around the Cartesian coordinate plane. Every second, he jumps from his current position $(x_p, y_p)$ to another lattice point $(x_q, y_q)$, such that no lattice point other than $(x_p, y_p)$ and $(x_q, y_q)$ lies on the segment between point $(x_p, y_p)$ and point $(x_q, y_q)$.

As Ian wants to meet Mary as soon as possible, he wants to jump towards point $(a,b)$ using at most $2$ jumps. Unfortunately, Ian is not good at maths. Can you help him?

A lattice point is defined as a point with both the $x$-coordinate and $y$-coordinate being integers.

Input

The first line contains a single integer $t$ ($1 \le t \le 500$) — the number of test cases. The description of test cases follows.

The first and only line of each test case contains two integers $a$ and $b$ ($1\le a,b\le 10^9$) — the coordinates of the lattice point where Mary lives.

Output

For each test case, print an integer $n$ ($1 \le n \le 2$) on the first line, denoting the number of jumps Ian uses in order to meet Mary. Note that you do not need to minimize the number of jumps.

On the $i$-th line of the next $n$ lines, print two integers $0 \le x_i,y_i \le 10^9$ separated by a space, denoting Ian's location $(x_i,y_i)$ after the $i$-th jump. $x_n = a$, $y_n = b$ must hold.

Ian's initial location and his locations after each of the $n$ jumps need not be distinct.

If there are multiple solutions, output any.

ExampleInput

8
3 4
4 4
3 6
2 2
1 1
7 3
2022 2023
1000000000 1000000000

Output

1
3 4
2
3 2
4 4
2
5 3
3 6
2
1 0
2 2
1
1 1
1
7 3
1
2022 2023
2
69420420 469696969
1000000000 1000000000

Note

In the first test case:

$(0,0) \to (3,4)$

In the second test case:

$(0,0) \to (3,2) \to (4,4)$

In the third test case:

$(0,0) \to (5,3) \to (3,6)$

题目大意：
Ian和Mary是生活在笛卡尔坐标系格点上的青蛙，Ian位于原点(0,0)，Mary位于(a,b)。Ian希望通过跳跃访问Mary，每次跳跃必须到达另一个格点，并且跳跃路径上不能有其他格点。Ian希望使用最多两次跳跃尽快到达Mary的位置。需要帮助Ian找到跳跃的路径。

输入数据格式：
第一行包含一个整数t（1≤t≤500），表示测试用例的数量。接下来每个测试用例包含一行，有两个整数a和b（1≤a,b≤10^9），表示Mary所在的格点坐标。

输出数据格式：
对于每个测试用例，首先输出一个整数n（1≤n≤2），表示Ian到达Mary所需的跳跃次数。然后在接下来的n行中，每行输出两个整数x_i和y_i（0≤x_i,y_i≤10^9），表示Ian第i次跳跃后的位置。最后，Ian的位置必须满足x_n=a, y_n=b。如果有多个解决方案，输出任意一个即可。

请注意，Ian的初始位置以及每次跳跃后的位置可以不唯一。题目大意： Ian和Mary是生活在笛卡尔坐标系格点上的青蛙，Ian位于原点(0,0)，Mary位于(a,b)。Ian希望通过跳跃访问Mary，每次跳跃必须到达另一个格点，并且跳跃路径上不能有其他格点。Ian希望使用最多两次跳跃尽快到达Mary的位置。需要帮助Ian找到跳跃的路径。 输入数据格式： 第一行包含一个整数t（1≤t≤500），表示测试用例的数量。接下来每个测试用例包含一行，有两个整数a和b（1≤a,b≤10^9），表示Mary所在的格点坐标。 输出数据格式： 对于每个测试用例，首先输出一个整数n（1≤n≤2），表示Ian到达Mary所需的跳跃次数。然后在接下来的n行中，每行输出两个整数x_i和y_i（0≤x_i,y_i≤10^9），表示Ian第i次跳跃后的位置。最后，Ian的位置必须满足x_n=a, y_n=b。如果有多个解决方案，输出任意一个即可。 请注意，Ian的初始位置以及每次跳跃后的位置可以不唯一。