Problem

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₁, y₁), (x₂, y₂) and (x₃, y₃), then the center for this triangle will have the coordinates ((x₁ + x₂ + x₃) / 3, (y₁ + y₂ + y₃) / 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 vertexes 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.

Input

The first line of input gives the number of cases, N. N test cases follow. Each test case consists of one line containing the integers n, A, B, C, D, x₀, y₀ 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₀, y₀ and M the following pseudocode will print the coordinates of the trees in the input set. mod 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

Output

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.

Limits

Time limit: 30 5 seconds per test set.

Memory limit: 1GB.

1 ≤ N ≤ 10,

0 ≤ A, B, C, D, x₀, y₀≤ 10⁹,

1 ≤ M ≤ 10⁹.

Small dataset (Test set 1 - Visible; 5 Points)

3 ≤ n ≤ 100.

Large dataset (Test set 2 - Hidden; 10 Points)

3 ≤ n ≤ 100000.

Sample

2
4 10 7 1 2 0 1 20
6 2 0 2 1 1 2 11

Case #1: 1
Case #2: 2

In the first test case, the 4 trees in the generated input set are (0, 1), (7, 3), (17, 5), (17, 7).