King's Circle

킥스타트리아 왕국은 오랜만에 축제 분위기입니다. 새 국왕의 즉위식이 열리고, 관례에 따라 왕실 퍼레이드가 수도의 거리를 행진합니다.

수도는 가로와 세로로 끝없이 뻗은 무한히 많은 도로가 1미터 간격으로 놓인 무한한 2차원 평면으로 볼 수 있습니다. 가로 도로는 위에서 아래로 음의 무한대부터 양의 무한대까지 번호가 붙어 있고, 세로 도로는 왼쪽에서 오른쪽으로 음의 무한대부터 양의 무한대까지 번호가 붙어 있습니다.

수도에는 $N$개의 카페가 있습니다. $i$번째 카페는 세로 도로 $V_i$와 가로 도로 $H_i$가 만나는 교차점에 있습니다. 두 카페가 같은 교차점에 있는 경우는 없습니다. 퍼레이드 기술자들이 중간에 들를 카페를 정확히 3개 고릅니다.

퍼레이드는 출발한 곳으로 돌아와야 하며, 경로는 변의 길이가 모두 같은 정사각형이어야 합니다. 각 카페는 정사각형의 변 위든 꼭짓점이든 어디에 있어도 됩니다.

어떤 카페 3개의 조합은 하나의 정사각형 위에 놓일 수 없습니다. 세 카페를 모두 지나는 정사각형 퍼레이드가 하나 이상 존재하는 카페 3개 조합의 개수를 구하세요. 두 조합이 다르다는 것은 한쪽에는 들어 있고 다른 쪽에는 없는 카페가 있다는 뜻입니다.

첫 줄에 테스트 케이스의 수 $T$가 주어집니다. 이어서 $T$개의 줄에 정수 10개 $N$, $V_1$, $H_1$, $A$, $B$, $C$, $D$, $E$, $F$, $M$이 주어집니다.

$N$은 카페의 수이며, 첫 번째 카페는 세로 도로 $V_1$과 가로 도로 $H_1$의 교차점에 있습니다.

$i = 2$부터 $N$까지 카페의 위치는 다음과 같이 생성됩니다.

$V_i = (A \times V_{i-1} + B \times H_{i-1} + C) \bmod M$

$H_i = (D \times V_{i-1} + E \times H_{i-1} + F) \bmod M$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력합니다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 하나의 정사각형 퍼레이드 위에 놓일 수 있는 카페 3개 조합의 개수입니다.

• $1 \le T \le 100$.
• $0 \le A, B, C, D, E, F < M$.
• $0 \le V_1, H_1 < M$.
• 모든 $i \ne j$에 대해 $(V_i, H_i) \ne (V_j, H_j)$.

예제 1에서 카페는 (1, 1), (1, 0), (0, 3), (4, 0)에 있습니다. (1, 1), (1, 0), (0, 3) 조합, (1, 1), (1, 0), (4, 0) 조합, (1, 0), (0, 3), (4, 0) 조합은 정사각형 퍼레이드가 지날 수 있습니다. (1, 1), (0, 3), (4, 0) 조합을 지나는 정사각형 퍼레이드는 없습니다.

예제 2에서 카페는 (3, 1), (4, 1), (5, 1), (6, 1), (7, 1), (8, 1)에 있습니다. 모두 같은 세로 도로 위에 있으므로 모든 3개 조합을 정사각형 퍼레이드가 지날 수 있습니다. 답은 6C3 = 20입니다.

예제 3에서 카페는 (7, 24), (19, 17), (0, 34)에 있습니다. 세 카페를 모두 지나는 정사각형 퍼레이드가 없으므로 답은 0입니다.

이 문제의 큰 데이터셋에는 인터프리터 언어나 느린 언어를 사용하지 않는 것을 권장합니다.