패러글라이딩

악당 그래펜도르프를 물리치기 위한 여정을 계속하려면, 우리의 영웅 에지는 신전에서 한 가지 도전을 극복해야 한다. 신전은 xy 평면 위의 이차원 공간이며, 평면의 x축을 따라 높이가 제각각인 N개의 탑이 세워져 있다. 각 탑은 2D 평면의 수직선분으로 나타낼 수 있다. 탑 i의 밑면은 ($p_{i}$, 0)에 있고, 꼭대기는 ($p_{i}$, $h_{i}$)에 있다. 또한 평면에는 K개의 풍선이 떠 있다. 각 풍선은 2D 평면의 한 점으로 나타낼 수 있으며, 풍선 i의 위치는 ($x_{i}$, $y_{i}$)이다. 에지는 이 도전에서 가능한 한 많은 풍선을 모아야 한다.

다행히 에지에게는 이 신전의 다른 방에서 발견한 믿음직한 패러글라이더가 있다. 그는 아무 탑이나 골라 올라간 뒤, 탑 위의 아무 위치에서나 x축의 양의 방향이나 음의 방향을 향해 활강할 수 있다. 활강할 때는 탑에 대해 45도 각도를 이루는 직선 경로로 하강한다. 에지는 탑에서 활강해 내려가는 도중 경로에 있는 모든 풍선을 모을 수 있다. 탑에 올라가 아무 위치에서나 뛰어내리는 이 과정을 원하는 만큼 반복할 수 있다. 하강 중 탑에 닿으면, 그 지점에서 탑 위에 있으며 올라가는 중인 것으로 간주한다. 에지는 xy 평면의 한 점이라고 가정해도 된다.

에지는 고대 기술로 만든 고글을 사용하여 각 탑과 풍선의 높이와 위치를 알아냈다. 이 정보를 이용해 에지가 이 신전에서 모을 수 있는 풍선의 최대 개수를 구하도록 도와주자.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 40초. 메모리 제한: 1 GB. 0 ≤ $A_{i}$ ≤ $10^{9}$, i = 1부터 4까지. 0 ≤ $B_{i}$ ≤ $10^{9}$, i = 1부터 4까지. 0 ≤ $C_{i}$ ≤ $10^{9}$, i = 1부터 4까지. 1 ≤ $M_{i}$ ≤ $10^{9}$, i = 1부터 4까지. 1 ≤ $p_{1}$, $p_{2}$ ≤ $10^{9}$. 1 ≤ $h_{1}$, $h_{2}$ ≤ $10^{9}$. 1 ≤ $x_{1}$, $x_{2}$ ≤ $10^{9}$. 1 ≤ $y_{1}$, $y_{2}$ ≤ $10^{9}$. i가 j = 1부터 N까지이고 i $ne; j일 때, $p_{i}$ ≠ $p_{j}$.

소규모 데이터 세트(테스트 세트 1 - 공개)

2 ≤ N ≤ 1000. 2 ≤ K ≤ 1000.

대규모 데이터 세트(테스트 세트 2 - 비공개)

2 ≤ N ≤ $10^{5}$. 2 ≤ K ≤ $10^{5}$.

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 다섯 줄로 이루어진다. 첫 줄에는 위에서 설명한 정수 N과 K가 주어진다. 다음 네 줄은 탑의 위치와 높이, 그리고 풍선의 x좌표와 y좌표를 생성하는 데 사용되는 점화식을 설명한다. 네 줄에는 각각 다음 형식으로 여섯 개의 정수가 주어진다.

• $p_{1}$ $p_{2}$ $A_{1}$ $B_{1}$ $C_{1}$ $M_{1}$

• $h_{1}$ $h_{2}$ $A_{2}$ $B_{2}$ $C_{2}$ $M_{2}$

• $x_{1}$ $x_{2}$ $A_{3}$ $B_{3}$ $C_{3}$ $M_{3}$

• $y_{1}$ $y_{2}$ $A_{4}$ $B_{4}$ $C_{4}$ $M_{4}$

$p_{i}$(범위: 3부터 N까지), $h_{i}$(범위: 3부터 N까지), $x_{i}$(범위: 3부터 K까지), $y_{i}$(범위: 3부터 K까지)의 값을 생성하기 위해 다음 점화식을 사용한다.

• i = 3부터 N까지, $p_{i}$ = ($A_{1}$ × $p_{i - 1}$ + $B_{1}$ × $p_{i - 2}$ + $C_{1}$)를 $M_{1}$로 나눈 나머지 + 1.

• i = 3부터 N까지, $h_{i}$ = ($A_{2}$ × $h_{i - 1}$ + $B_{2}$ × $h_{i - 2}$ + $C_{2}$)를 $M_{2}$로 나눈 나머지 + 1.

• i = 3부터 K까지, $x_{i}$ = ($A_{3}$ × $x_{i - 1}$ + $B_{3}$ × $x_{i - 2}$ + $C_{3}$)를 $M_{3}$로 나눈 나머지 + 1.

• i = 3부터 K까지, $y_{i}$ = ($A_{4}$ × $y_{i - 1}$ + $B_{4}$ × $y_{i - 2}$ + $C_{4}$)를 $M_{4}$로 나눈 나머지 + 1.

서로 같은 위치에 있는 두 탑은 없다는 것이 보장된다. 그러나 탑과 풍선이 겹칠 수는 있다. 이 경우 해당 풍선을 모을 수 있다고 가정한다. 둘 이상의 풍선이 한 점에 있을 수도 있다는 점에 유의하라. 이 경우 에지는 그 점을 통과하여 해당 풍선을 모두 한 번에 모을 수 있다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 에지가 모을 수 있는 풍선의 최대 개수이다.

샘플 케이스 #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]$.