Crop Triangles (Large)

A few pranksters have watched too much of the documentary channel, so they decided to build a crop triangle overnight. The stage is a wide field that looks like an evenly spaced grid from above. Some trees are planted in the field, and every tree stands on a point where two grid lines meet (a grid point). The pranksters want the three vertices of their triangle to sit on trees. To make it more interesting, they also want the centroid of the triangle to land on a grid point. For a triangle with vertices $(x_1, y_1)$, $(x_2, y_2)$ and $(x_3, y_3)$, the centroid is $\left(\frac{x_1 + x_2 + x_3}{3}, \frac{y_1 + y_2 + y_3}{3}\right)$.

You are given the integer coordinates of every tree in the field. Count the triangles formed by three distinct trees whose centroid has integer coordinates in both axes.

If the three trees are collinear the area is 0, and such a triangle still counts.

The first line contains the number of test cases $N$. $N$ test cases follow. Each test case is one line holding 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 come out in the order the following pseudocode prints them. mod is the remainder operation.

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 coordinate appears twice.

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 100000$

For each test case, print one line starting with Case #X: , where $X$ is the test case number starting from 1. Follow it with the integer number of triangles that have three distinct trees as vertices and a centroid on a grid point.

In the first test case of the example input, the four trees that are generated are $(0, 1)$, $(7, 3)$, $(17, 5)$ and $(17, 7)$.