King's Circle

For the first time in living memory, the Kingdom of Kickstartia is celebrating. The new King is being crowned today, and as is customary for a coronation, a Royal Parade will march through the streets of the capital.

The capital is an infinite 2D plane with infinitely many, infinitely long streets, spaced one meter apart, running horizontally and vertically. The horizontal streets are numbered from negative infinity to infinity from top to bottom, and the vertical streets are numbered from negative infinity to infinity from left to right.

There are $N$ cafes in the capital. The $i$-th cafe is located at the intersection of vertical street $V_i$ and horizontal street $H_i$. No two cafes share an intersection. You will pick exactly three of these cafes for the parade technicians to stop at along the way.

The parade must end where it starts, and its path must form a square with straight sides of equal length. Each cafe can be anywhere along the square, on a side or at a corner.

Some sets of three cafes cannot lie on a single such square. Count the number of different sets of three cafes for which at least one square parade passes through all three. Two sets are different if and only if one contains a cafe that the other does not.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains ten integers $N$, $V_1$, $H_1$, $A$, $B$, $C$, $D$, $E$, $F$, and $M$.

$N$ is the number of cafes, and the first cafe is at the intersection of vertical street $V_1$ and horizontal street $H_1$.

For $i = 2$ to $N$, the locations are generated as follows.

$V_i = (A \times V_{i-1} + B \times H_{i-1} + C) \bmod M$

$H_i = (D \times V_{i-1} + E \times H_{i-1} + F) \bmod M$

For each test case, output one line in the format Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of sets of three cafes that lie on a common square parade.

• $1 \le T \le 100$.
• $0 \le A, B, C, D, E, F < M$.
• $0 \le V_1, H_1 < M$.
• For all $i \ne j$, $(V_i, H_i) \ne (V_j, H_j)$.

In Sample Case #1, there are four cafes at (1, 1), (1, 0), (0, 3), and (4, 0). A square parade can pass through the set (1, 1), (1, 0), (0, 3), the set (1, 1), (1, 0), (4, 0), or the set (1, 0), (0, 3), (4, 0). No square parade passes through the set (1, 1), (0, 3), (4, 0).

In Sample Case #2, there are 6 cafes at (3, 1), (4, 1), (5, 1), (6, 1), (7, 1), and (8, 1). They all lie on the same vertical street, so every triplet has a square parade through it. The answer is 6 choose 3 = 20.

In Sample Case #3, there are 3 cafes at (7, 24), (19, 17), and (0, 34). No square parade passes through all three, so the answer is 0.

We do not recommend interpreted or slower languages for the Large dataset of this problem.