G. Knight Polygon
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ are considered to be a knight-move apart if exactly one of the following conditions holds:

  • $$$|x_1 - x_2| = 2$$$ and $$$|y_1 - y_2| = 1$$$
  • $$$|x_1 - x_2| = 1$$$ and $$$|y_1 - y_2| = 2$$$

Notice that this definition closely matches how a knight moves in chess. For example, here are three pairs of points that are a knight-move apart:

You are given integers $$$p$$$ and $$$q$$$. Find a simple lattice polygon whose area is $$$p/q$$$, where each pair of adjacent vertices is a knight-move apart, or state that no such polygon exists.

A polygon is simple if there are exactly two edges touching each vertex, and no two edges of the polygon intersect except at its vertices. A polygon is a lattice polygon if the coordinates of each of its vertices are integers.

Input

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

Each test case consists of a single line containing two integers $$$p$$$ and $$$q$$$ ($$$1 \le p, q \le 10^4$$$) — the numerator and denominator of the desired area, respectively.

Output

For each test case, if there is no solution, output a single integer $$$-1$$$.

Otherwise, the first line of output for each test case should contain a single integer $$$n$$$ ($$$3 \le n \le 10^5$$$) — the number of vertices in your polygon.

The next $$$n$$$ lines of output should each contain two integers $$$x$$$ and $$$y$$$ ($$$-10^9 \le x, y \le 10^9$$$) — the vertices of your polygon in either clockwise or counterclockwise order.

Your polygon should be simple, have an area of $$$\frac{p}{q}$$$, and each pair of adjacent vertices should be a knight-move apart.

If there are multiple solutions, print any.

Example
Input
4
18 3
1 2
8 1
20 3
Output
6
0 0
2 1
1 3
0 1
-1 3
-2 1
-1
14
-1 -2
-3 -1
-2 1
-1 3
0 1
1 3
2 1
3 -1
1 -2
2 0
1 2
0 0
-1 2
-2 0
-1
Note

Here is the polygon described by the output of the first test case, with an area of $$$\frac{18}{3} = 6$$$:

Here is the polygon described by the output of the third test case, with an area of $$$\frac{8}{1} = 8$$$:

For the second and fourth test cases, we can show that no valid polygon exists.