Description

一些恶作剧者看了太多的 Discovery Channel，现在他们想在夜晚建造一个“作物三角形”。他们想要在一片看起来像均匀网格的大农田里建造这个三角形。从上方看，农田是一个均匀分布的网格。有一些树被种在田地里，每棵树都位于两条网格线的交点（即网格点）上。恶作剧者希望他们的作物三角形的顶点都位于这些树上。此外，为了让三角形更有趣，他们还希望三角形的中心也位于某个网格点上。我们提醒你，如果一个三角形的顶点分别为 $(x_1, y_1)$、$(x_2, y_2)$ 和 $(x_3, y_3)$，那么该三角形的中心坐标为 $((x_1 + x_2 + x_3) / 3, (y_1 + y_2 + y_3) / 3)$。

你将获得一组整数坐标点，表示所有树在网格上的位置。请你计算，在这些点中可以选出多少个不同的三元组，使得它们组成的三角形的中心也是一个网格点（即中心坐标也是整数）。

如果三角形的面积为 $0$，我们仍然认为它是一个合法的三角形。

Input Format

第一行输入一个整数 $N$，表示测试用例的数量。接下来有 $N$ 组测试数据。每组测试数据占一行，包含整数 $n$、$A$、$B$、$C$、$D$、$x_0$、$y_0$ 和 $M$，用一个空格隔开。$n$ 表示树的数量。利用 $n$、$A$、$B$、$C$、$D$、$x_0$、$y_0$ 和 $M$，可以按照如下伪代码生成所有树的坐标。$mod$ 表示取余操作。

保证生成的树的坐标不会重复。

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 Format

对于每组测试数据，输出一行，格式为 "Case #$X$: "，其中 $X$ 是测试用例编号（从 $1$ 开始）。后接一个整数，表示可以选出的满足条件的三角形数量。

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

Case #1: 1
Case #2: 2

Hint

样例解释

在第一个测试用例中，生成的 $4$ 棵树的坐标分别为 $(0, 1)$、$(7, 3)$、$(17, 5)$、$(17, 7)$。

数据范围

• $1 \leq N \leq 10$，
• $0 \leq A, B, C, D, x_0, y_0 \leq 10^9$，
• $1 \leq M \leq 10^9$。

小数据范围（5 分，测试点 1 - 可见）

• $3 \leq n \leq 100$。

大数据范围（10 分，测试点 2 - 隐藏）

• $3 \leq n \leq 100000$。

由 ChatGPT 4.1 翻译