Find C

Two friends stand at $A$ and $B$, two distinct lattice points in the plane. To fit both of them in one photo you pick a lattice point $C$ that satisfies all of the following.

1. $C$ differs from $A$ and from $B$.
2. Segment $AC$ contains no lattice point other than its two endpoints.
3. Segment $BC$ contains no lattice point other than its two endpoints.
4. Triangle $ABC$ has area greater than $0$, so $C$ does not lie on the line through $A$ and $B$.
5. No lattice point lies strictly inside triangle $ABC$.

A point whose $x$ coordinate and $y$ coordinate are both integers is a lattice point.

Nobody takes a single snap, so for the given $A$ and $B$ you need $K$ such points $C$. Infinitely many points satisfy the conditions, so the output section fixes which $K$ of them you print.

The first line contains the number of test cases $T$. ($1 \le T \le 1000$)

Each of the next $T$ lines contains five integers $A_x$, $A_y$, $B_x$, $B_y$, $K$. The two points $A = (A_x, A_y)$ and $B = (B_x, B_y)$ are distinct. ($-10^9 \le A_x, A_y, B_x, B_y \le 10^9$, $0 \le K$, the sum of all $K$ is at most $20000$)

For each test case print $K$ lines, each holding the coordinates of one point $C$ in the format "$C_x$ $C_y$". A test case with $K = 0$ prints nothing.

Choose the $K$ points this way. Among the lattice points $C$ that satisfy every condition above, keep only those with

$s(C) = (B_x - A_x)(C_y - A_y) - (B_y - A_y)(C_x - A_x) > 0$

and

$f(C) = (C_x - A_x)(B_x - A_x) + (C_y - A_y)(B_y - A_y) \ge 0.$

Print $K$ of the kept points in increasing order of $f(C)$, starting from the smallest.

Infinitely many points remain, so $K$ of them always exist, and the kept points have pairwise different values of $f(C)$, so the output is unique. Every coordinate chosen by this rule has absolute value at most $10^{14}$.