왕의 순환로

기억이 닿는 한 처음으로, Kickstartia 왕국이 축제로 활기를 띠고 있다. 새 왕의 대관식 날이기 때문이다. 대관식의 관례에 따라, Royal Parade가 수도의 거리를 따라 행진할 것이다.

수도는 무한한 2D 평면으로 생각할 수 있으며, 수평과 수직으로 뻗은 무한히 길고 무한히 많은 거리들이 일 미터 간격으로 배치되어 있다. 수평 거리는 위에서 아래로 음의 무한대부터 무한대까지 번호가 붙어 있고, 수직 거리는 왼쪽에서 오른쪽으로 음의 무한대부터 무한대까지 번호가 붙어 있다.

수도에는 N개의 카페가 있으며, i번째 카페는 수직 거리 $V_{i}$와 수평 거리 $H_{i}$의 교차점에 있다. 같은 교차점에 있는 두 카페는 없다. 퍼레이드 기술자들이 만족스럽게 배불리 지낼 수 있도록, 도중에 들를 카페로 이들 중 정확히 세 곳을 고른다.

혼란에 어느 정도 질서를 부여하기 위해, 퍼레이드는 시작한 곳에서 끝나야 하고 거리를 지나는 경로는 정사각형 모양이어야 한다고 추가로 정했다. 이 정사각형의 변은 직선이며 모두 길이가 같다. 각 카페는 정사각형 위의 어디에든 있을 수 있다. 즉, 변 위나 꼭짓점에 있을 수 있다.

이로 인해 곧바로 문제가 생긴다. 어떤 세 카페를 고르느냐에 따라, 그 세 카페를 지나는 정사각형 퍼레이드를 만드는 것이 불가능할 수도 있다. 따라서 과제는 다음을 알아내는 것이다. 집합에 속한 세 카페를 모두 포함하는 정사각형 퍼레이드가 적어도 하나 존재하도록 하는 서로 다른 세 카페의 집합은 몇 개인가? (한 집합에는 있지만 다른 집합에는 없는 카페가 있을 때, 그리고 그럴 때에만 두 집합은 서로 다르다.)

제한

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 100초. 메모리 제한: 1 GB. 0 ≤ A < M. 0 ≤ B < M. 0 ≤ C < M. 0 ≤ D < M. 0 ≤ E < M. 0 ≤ F < M. 0 ≤ $V_{1}$ < M. 0 ≤ $H_{1}$ < M. 모든 i ≠ j에 대해, ($V_{i}$, $H_{i}$) ≠ ($V_{j}$, $H_{j}$).

작은 데이터 세트 (테스트 세트 1 - 공개)

3 ≤ N ≤ 1000. 2 ≤ M ≤ 1000.

큰 데이터 세트 (테스트 세트 2 - 비공개)

3 ≤ N ≤ 5 × $10^{5}$. 2 ≤ M ≤ $10^{6}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 열 개 N, $V_{1}$, $H_{1}$, A, B, C, D, E, F, M을 포함하는 한 줄로 이루어진다.

N은 카페의 수이다. 첫 번째 카페는 수직 거리 $V_{1}$와 수평 거리 $H_{1}$의 교차점에 있다.

나머지 카페의 위치 $V_{i}$, $H_{i}$는 i = 2부터 N까지 다음과 같이 생성할 수 있다.

• $V_{i}$ = (A × $V_{i-1}$ + B × $H_{i-1}$ + C)를 M으로 나눈 나머지

• $H_{i}$ = (D × $V_{i-1}$ + E × $H_{i-1}$ + F)를 M으로 나눈 나머지

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작), y는 위에서 설명한 조건을 만족하는 카페 집합의 수이다.

예제 케이스 #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에는 6개의 카페가 있으며, 위치는 (3, 1), (4, 1), (5, 1), (6, 1), (7, 1), (8, 1)이다. 이들이 모두 같은 수직 거리에 있으므로, 카페로 이루어진 모든 세쌍에는 그 세 카페를 지나는 정사각형 퍼레이드가 존재한다. 따라서 답은 6에서 3 = 20를 고르는 경우의 수이다.

예제 케이스 #3에는 3개의 카페가 있으며, 위치는 (7, 24), (19, 17), (0, 34)이다. 이 카페들을 지나는 정사각형 퍼레이드는 없으므로, 답은 0이다.

참고: 이 문제의 큰 데이터 세트에는 인터프리터 방식의 느린 언어를 사용하지 않는 것을 권장한다.