크롭 트라이앵글 (라지)

장난꾼 몇 명이 다큐멘터리 채널을 너무 많이 본 끝에 밤사이 밭에 크롭 트라이앵글을 만들기로 했다. 위에서 내려다보면 일정한 간격의 격자처럼 보이는 넓은 밭이 무대다. 밭에는 나무가 몇 그루 심겨 있고, 나무는 모두 격자선이 만나는 점(격자점) 위에 서 있다. 장난꾼은 삼각형의 세 꼭짓점을 나무 위에 두려고 한다. 여기에 재미를 더하려고 삼각형의 무게중심도 격자점에 놓이게 하려 한다. 세 꼭짓점이 $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$인 삼각형의 무게중심은 $\left(\frac{x_1 + x_2 + x_3}{3}, \frac{y_1 + y_2 + y_3}{3}\right)$이다.

밭에 있는 모든 나무의 정수 좌표가 주어진다. 서로 다른 세 나무를 꼭짓점으로 골라 만든 삼각형 가운데 무게중심의 두 좌표가 모두 정수인 것이 몇 개인지 구한다.

세 나무가 한 직선 위에 있어 면적이 0이 되는 경우도 삼각형으로 센다.

첫째 줄에 테스트 케이스의 개수 $N$이 주어진다. 이어서 $N$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄이고, 정수 $n$, $A$, $B$, $C$, $D$, $x_0$, $y_0$, $M$이 공백 한 칸으로 구분되어 주어진다. $n$은 나무의 개수다.

나무의 좌표는 다음 의사 코드가 출력하는 순서와 같다. 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

좌표가 같은 나무가 두 번 나오지 않도록 매개변수가 주어진다.

제한

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

각 테스트 케이스마다 한 줄에 Case #X: 를 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호다. 그 뒤에 서로 다른 세 나무를 꼭짓점으로 하고 무게중심이 격자점인 삼각형의 개수를 정수로 출력한다.

예제 입력의 첫 테스트 케이스에서 만들어지는 나무 네 그루의 좌표는 $(0, 1)$, $(7, 3)$, $(17, 5)$, $(17, 7)$이다.