D. Rudraksh's Sleepiness
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Rudraksh is a school kid. But he is sleepy boy. He often gets late for his school. Also, he is famous among his friends for his knowledge and love towards prime numbers.

One day he woke up and saw that he was extremely late for his school, so he started mapping his school and home on the city's map. He marked his home to be at $$$(0,0)$$$ and school to be at $$$(x,y)$$$ where $$$x$$$ and $$$y$$$ both are positive integers. He will reach his school by making some intermediate stops in the path.

Now as he loves primes too much he will choose the path in such a way that for each two adjacent stops the Manhattan distance between them is a prime number. More formally, he can start from $$$(a,b)$$$ and stop at $$$(c,d)$$$ if and only if $$$|a-c|+|b-d|$$$ is a prime number. He wants to reach the school by making the minimum number of stops in his path. Find the minimum number of stops Rudraksh needs to take to reach school. Also find the stops he will take in his path.

Note that Rudraksh should not step out of his city boundaries i.e. at any time his x-coordinate should be between $$$0$$$ and $$$x$$$ (inclusive), and y-coordinate should be between $$$0$$$ and $$$y$$$ (inclusive).

Input

The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$  — the number of test cases.

For each test case, you will be provided with two positive integers $$$x$$$ $$$(1 \leq x \leq 10^7)$$$ and $$$y$$$ $$$(1 \leq y \leq 10^7)$$$  — the coordinates of the school mapped by Rudraksh.

It is guaranteed that sum of $$$(x+y)$$$ over all testcases will be less than or equal to $$$10^7$$$.

Output

For each test case:

First print the integer $$$n$$$, which is the minimum number of stops Rudraksh took to reach school.

Now print $$$n$$$ lines each containing two non-negative integers $$$x_i$$$ $$$(0 \leq x_i \leq x)$$$ and $$$y_i$$$ $$$(0 \leq y_i \leq y)$$$  — the coordinates of the $$$i_{th}$$$ stop made by Rudraksh.

For each $$$i$$$ $$$(1 \le i < n)$$$, $$$|x_{i+1}-x_i| + |y_{i+1}-y_i|$$$ should be a prime number. Also, $$$x_1+y_1$$$ should be a prime number (as starting from origin).

The last stop should be his school coordinates. You don't need to print $$$(0,0)$$$.

If there are multiple answers, print any of them.

Example
Input
3
1 1
2 10
5 5
Output
1
1 1
2
0 5
2 10
2
3 0
5 5