Knight Polygon

Two points $(x_1, y_1)$ and $(x_2, y_2)$ are 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$

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.

The first line contains a single integer $t$ ($1 \le t \le 10$), the number of test cases. Each test case consists of a single line with two integers $p$ and $q$ ($1 \le p, q \le 10^4$), the numerator and denominator of the desired area.

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

Otherwise, the first line should contain a single integer $n$ ($3 \le n \le 10^5$), the number of vertices in your polygon. The next $n$ lines 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 must be simple, have an area of $\frac{p}{q}$, and have every pair of adjacent vertices a knight-move apart. If there are multiple solutions, print any of them.

The polygon described by the output of the first test case, with an area of $\frac{18}{3} = 6$, is shown below.

The polygon described by the output of the third test case, with an area of $\frac{8}{1} = 8$, is shown below.

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