패러글라이딩

악당 Graphendorf를 쓰러뜨리는 여정을 이어 가려면 영웅 Edge가 신전의 시련을 넘어야 한다. 신전은 xy 평면이며, x축을 따라 높이가 서로 다른 탑 $N$개가 세워져 있다. 탑 $i$는 밑점이 $(p_i, 0)$, 꼭대기가 $(p_i, h_i)$인 수직 선분이다. 평면에는 풍선 $K$개가 떠 있고, 풍선 $i$는 점 $(x_i, y_i)$에 있다. Edge는 풍선을 최대한 많이 모으려 한다.

Edge에게는 패러글라이더가 있다. 그는 아무 탑이나 올라가, 탑의 임의의 위치에서 x축의 양의 방향 또는 음의 방향으로 활강할 수 있다. 활강할 때는 탑에 대해 45도를 이루는 직선 경로로 내려간다. 활강 경로에 있는 풍선은 모두 모을 수 있다. 탑에 올라가 뛰어내리는 과정은 몇 번이고 반복할 수 있다. 하강 중 탑에 닿으면 그 지점에서 탑 위에 있는 것으로 보며, 거기서 다시 올라갈 수 있다. Edge는 xy 평면 위의 한 점으로 취급한다.

Edge는 신전의 다른 방에서 패러글라이더를 발견했다. 고대 기술로 만든 고글을 써서 각 탑과 풍선의 위치와 높이를 알아냈다. 이 정보를 바탕으로 Edge가 이 신전에서 모을 수 있는 풍선의 최대 개수를 구하라.

첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다섯 줄로 이루어진다. 첫 줄에는 $N$과 $K$가 주어진다. 이어지는 네 줄에는 각각 정수 여섯 개가 주어진다.

p1 p2 A1 B1 C1 M1
h1 h2 A2 B2 C2 M2
x1 x2 A3 B3 C3 M3
y1 y2 A4 B4 C4 M4

나머지 값은 다음 점화식으로 생성한다.

$p_i = (A_1 \times p_{i-1} + B_1 \times p_{i-2} + C_1) \bmod M_1 + 1 \quad \text{단, } i = 3 \text{부터 } N\text{까지}$

$h_i = (A_2 \times h_{i-1} + B_2 \times h_{i-2} + C_2) \bmod M_2 + 1 \quad \text{단, } i = 3 \text{부터 } N\text{까지}$

$x_i = (A_3 \times x_{i-1} + B_3 \times x_{i-2} + C_3) \bmod M_3 + 1 \quad \text{단, } i = 3 \text{부터 } K\text{까지}$

$y_i = (A_4 \times y_{i-1} + B_4 \times y_{i-2} + C_4) \bmod M_4 + 1 \quad \text{단, } i = 3 \text{부터 } K\text{까지}$

탑의 위치는 모두 다르다. 즉 $i, j = 1$부터 $N$까지이고 $i \neq j$이면 $p_i \neq p_j$이다. 탑과 풍선이 겹칠 수 있으며, 이 경우 Edge는 그 풍선을 모을 수 있다. 여러 풍선이 같은 점에 있을 수 있으며, 그 점을 지나면 풍선을 모두 한 번에 모을 수 있다.

각 테스트 케이스마다 Case #x: y 형식의 줄을 하나 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 Edge가 모을 수 있는 풍선의 최대 개수이다.

• $1 \le T \le 100$
• $0 \le A_i \le 10^9$ ($i = 1$부터 $4$까지)
• $0 \le B_i \le 10^9$ ($i = 1$부터 $4$까지)
• $0 \le C_i \le 10^9$ ($i = 1$부터 $4$까지)
• $1 \le M_i \le 10^9$ ($i = 1$부터 $4$까지)
• $1 \le p_1, p_2 \le 10^9$
• $1 \le h_1, h_2 \le 10^9$
• $1 \le x_1, x_2 \le 10^9$
• $1 \le y_1, y_2 \le 10^9$

예제 1의 입력은 문제에 나온 상황을 만든다. 생성되는 배열은 $p = [1, 4, 6]$, $h = [4, 1, 3]$, $x = [2, 5]$, $y = [4, 1]$이다.

예제 2에서 생성되는 배열은 $p = [2, 4, 6, 8, 10]$, $h = [4, 4, 4, 4, 4]$, $x = [1, 4, 6, 11, 5]$, $y = [3, 5, 3, 3, 1]$이다.