Crop Triangles (Hard)

*Note that this is a harder version of the problem
cropeasy.*

Some pranksters have watched too much Discovery Channel and
now they want to build a crop triangle during the night. They
want to build it inside a large crop that looks like an evenly
spaced grid from above. There are some trees planted on the
field. Each tree is situated on an intersection of two grid
lines (a grid point). The pranksters want the vertices of their
crop triangle to be located at these trees. Also, for their
crop triangle to be more interesting they want the
*center* of that triangle to be located at some grid
point as well. We remind you that if a triangle has the
vertices $(x_1, y_1), (x_2,
y_2)$ and $(x_3,
y_3)$, then the center for this triangle will have the
coordinates $((x_1 + x_2 + x_3) /
3, (y_1 + y_2 + y_3) / 3)$.

You will be given a set of points with integer coordinates
giving the location of all the trees on the grid. You are asked
to compute how many triangles you can form with
*distinct* vertices in this set of points so that their
center is a grid point as well (i.e. the center has integer
coordinates).

If a triangle has area 0 we will still consider it a valid triangle.

The first line of input gives the number of cases, $T$.

$T$ test cases follow. Each test case consists of one line containing the integers $n, A, B, C, D, x_0, y_0$ and $M$ separated by exactly one space. $n$ will be the number of trees in the input set.

Using the numbers $n, A, B, C, D, x_0, y_0$ and $M$ the following pseudocode will print the coordinates of the trees in the input set. $\bmod $ indicates the remainder operation. The parameters will be chosen such that the input set of trees will not have duplicates.

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

You can assume that $1\leq T\leq 10; 0\leq A, B, C, D, x_0, y_0 \leq 10^9; 1\leq M\leq 10^9$ and $3\leq n\leq 100\, 000$.

For each test case, output one line containing "Case #$X$: " where $X$ is the test case number (starting from 1). This should be followed by an integer indicating the number of triangles which can be located at 3 distinct trees and has a center that is a grid point.

Sample Input 1 | Sample Output 1 |
---|---|

2 4 10 7 1 2 0 1 20 6 2 0 2 1 1 2 11 |
Case #1: 1 Case #2: 2 |