Ian Visits Mary
Contest: Codeforces Round 865 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, geometry, number theory

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 format:
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 format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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)$$$

Example input:
8
3 4
4 4
3 6
2 2
1 1
7 3
2022 2023
1000000000 1000000000

Example 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

Editorial:
Consider two points $$$(0,0)$$$ and $$$(x,y)$$$ (where not both of $$$x$$$ and $$$y$$$ are $$$0$$$). We show that no lattice point lies on the segment joining the two points except the two endpoints if and only if $$$gcd(x,y)=1$$$.
We let $$$g=gcd(x,y)$$$. Then, a point $$$(x',y')$$$ lies on the segment joining $$$(0,0)$$$ and $$$(x,y)$$$ translates to that $$$x':y'=x:y$$$. If $$$g\ne1$$$, it means that we can let $$$x'=\frac xg$$$ and $$$y'=\frac yg$$$ to get a point lying on the interior of the segment joining $$$(0,0)$$$ and $$$(x,y)$$$. If $$$g=1$$$, this means that we cannot further simplify the ratio $$$x:y$$$, so we cannot get suitable $$$x',y'$$$.
Then, let us show that Ian can get to Mary within two moves. Indeed, consider $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ where $$$x_2-x_1=1$$$, since the value of the $$$x$$$-coordinates of a point lying on the segment joining $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$, and is not at the endpoints, is strictly between $$$x_1$$$ and $$$x_2$$$, but there are no integers strictly between $$$x_1$$$ and $$$x_2$$$, the point must not be a lattice point. Similarly, no lattice points lie on the segment joining $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ with $$$y_2-y_1=1$$$ except for the endpoints. Therefore, Ian can jump from $$$(0,0)$$$ to $$$(x-1,1)$$$ to $$$(x,y)$$$.
So, for any $$$(x,y)$$$, we first check if Ian can directly jump from $$$(0,0)$$$ to $$$(x,y)$$$ by checking if $$$gcd(x,y)=1$$$. If not, Ian can jump from $$$(0,0)$$$ to $$$(x-1,1)$$$ to $$$(x,y)$$$.