Transforming Comets

While traveling from Earth to Krypton, Superman was caught in a wormhole and instantly transported to an unknown location. He remembers the periodic comets he used to watch from Earth, and from his new position he can also see some periodic comets. He would like to use them to get his bearings, but first he must work out which comet is which.

These comets are periodic Gaussian hyper-comets. A periodic Gaussian hyper-comet is a sequence $(p_1, p_2, \ldots, p_n)$ where each $p_i = (x_i, y_i)$ is a point with integer coordinates. The comet visits $p_i$ and then $p_{i+1}$; the sequence is periodic, so after $p_n$ it visits $p_1$ again (indices are taken modulo $n$). A Gaussian hyper-comet also satisfies $p_i \neq p_{i+1}$ for every $i$, and $p_1 \neq p_n$.

Superman was disoriented in both space and time. In space, a comet he once knew may now appear rotated, scaled uniformly by the same positive factor on both axes, and/or translated. In time, the point he remembers as the first point may no longer be listed first.

For example, the right-triangular hyper-comet $((0,0),(1,0),(0,1))$ seen from Earth might now appear as $((40,40),(20,20),(60,20))$ or as $((20,20),(60,20),(40,40))$. Reversing space or time is not allowed: this comet can never appear as $((0,1),(1,0),(0,0))$.

Given one Gaussian hyper-comet as seen from Earth and one as seen from Superman's current location, decide whether they could be the same comet.

The first line contains an integer $t$ ($1 \le t \le 10$), the number of test cases.

Each test case begins with an integer $n$ ($2 \le n \le 500\,000$). The next $n$ lines each contain two space-separated integers $x_i\ y_i$ ($i = 1 \ldots n$), the points of the comet seen from Earth. Then $n$ more lines follow, each containing two space-separated integers $x'_i\ y'_i$, the points of the comet seen from Superman's current location.

All coordinates are integers between $0$ and $30\,000$ inclusive. For each comet, $p_i \neq p_{i+1}$ for every $i$ and $p_1 \neq p_n$.

For each test case, print the smallest positive integer $s$ such that the Earth point $p_1 = (x_1, y_1)$ can correspond to the current point $q_s = (x'_s, y'_s)$ under the disorientation described above (rotation, uniform scaling, translation, and a cyclic time shift, with no reflection and no time reversal). If the two comets cannot be the same, print $0$.