Crop Triangles (Small)

A few pranksters want to flatten a large triangle into a wheat field overnight. Seen from above the field is an evenly spaced grid, and trees grow at some of the grid points where two grid lines cross. The pranksters want all three vertices of the triangle to sit on trees. They also want the center of the triangle to land on a grid point.

The center of a triangle with vertices $(x_1, y_1)$, $(x_2, y_2)$ and $(x_3, y_3)$ is $\left(\dfrac{x_1 + x_2 + x_3}{3}, \dfrac{y_1 + y_2 + y_3}{3}\right)$.

You are given the integer coordinates of every tree on the field. Count the triangles whose three vertices are three distinct trees and whose center has integer coordinates in both axes. A triangle of area 0 counts as a valid triangle.

The first line contains the number of test cases $N$. Each of the next $N$ lines contains the integers $n$, $A$, $B$, $C$, $D$, $x_0$, $y_0$ and $M$ separated by exactly one space. $n$ is the number of trees.

The coordinates of the trees are the values printed by the pseudocode below, driven by those eight numbers. mod is the remainder operation. The first tree uses $x_0$ and $y_0$ as given, without the remainder, so it can exceed $M$.

X = x0, Y = y0
print X, Y
for i = 1 to n-1
  X = (A * X + B) mod M
  Y = (C * Y + D) mod M
  print X, Y

The parameters are chosen so that no two trees share a position.

Limits:

• $1 \le N \le 10$
• $0 \le A, B, C, D, x_0, y_0 \le 10^9$
• $1 \le M \le 10^9$
• $3 \le n \le 100$

For each test case, print one line of the form Case #X: Y, where $X$ is the test case number starting from 1 and $Y$ is the number of triangles whose vertices are three distinct trees and whose center is a grid point.

In the first test case of the first sample, the eight numbers generate the four trees $(0, 1)$, $(7, 3)$, $(17, 5)$ and $(17, 7)$.