페어랜드 (라지)

문제

페어랜드는 회사의 조직과 급여를 다음 법으로 규정한다.

회사마다 대표는 정확히 한 명이고, 대표에게는 상사가 없다.
대표를 제외한 모든 직원에게는 상사가 정확히 한 명 있다. 즉 회사의 조직도는 사이클이 없는 트리다.
직원이 회사에 남아 있는 동안 그 직원의 상사는 바뀌지 않는다. 어떤 상사가 회사를 떠나면 그 상사에게 보고하던 직원도 모두 떠나야 한다.
대표는 회사를 떠나지 않는다.
모든 직원은 연봉을 받는다. 직원의 연봉은 바뀌지 않는다.
직원마다 연봉이 다를 수 있고, 연봉은 조직도에서의 위치와 아무 관계가 없다.

여기에 법이 하나 더 생겼다.

회사 전체에서 가장 높은 연봉과 가장 낮은 연봉의 차이는 $D$ 이하여야 한다.

마리는 페어랜드 제너럴 스터프 사의 대표이고, 회사가 새 법을 지키도록 만들어야 한다. 그러려면 직원 일부를 내보내야 할 수도 있다. 마리는 직원 명단과 각 직원의 상사, 각 직원의 연봉을 알고 있다. 마리 자신을 포함해 남길 수 있는 직원 수의 최댓값을 구하라.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 직원 수 $N$ 과 허용되는 연봉 차이의 최댓값 $D$ 가 공백으로 구분되어 주어진다. 둘째 줄에는 정수 네 개 $S_0$ , $A_s$ , $C_s$ , $R_s$ 가, 셋째 줄에는 정수 네 개 $M_0$ , $A_m$ , $C_m$ , $R_m$ 이 공백으로 구분되어 주어진다. 이 여덟 개의 정수는 다음 두 수열을 정의한다.

$S_{i+1} = (S_i \times A_s + C_s) \bmod R_s$

$M_{i+1} = (M_i \times A_m + C_m) \bmod R_m$

마리의 직원 번호는 0이고 나머지 직원의 번호는 1부터 $N-1$ 까지다. 직원 $i$ 의 연봉은 $S_i$ 다. 마리를 제외한 직원 $i$ 의 상사는 $M_i \bmod i$ 다. 따라서 $M_0$ 은 마리의 상사와 무관하다. 마리에게는 상사가 없다.

제한

$1 \le T \le 100$
$1 \le N \le 10^6$ 이고, 모든 테스트 케이스의 $N$ 을 합한 값은 $10^6$ 이하다
$1 \le D \le 10^6$
$1 \le R_s, R_m \le 10^6$
$0 \le S_0 < R_s$
$0 \le M_0 < R_m$
$0 \le A_s, A_m \le 1000$
$0 \le C_s, C_m \le 10^9$

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 법 1번부터 7번까지를 모두 지키면서 마리가 자기 자신을 포함해 남길 수 있는 직원 수의 최댓값이다.

설명

첫 번째 예제 입력의 첫 테스트 케이스에는 대표뿐이고 다른 직원이 없다. 어떤 법도 어기지 않으므로 아무도 내보내지 않는다.

두 번째 테스트 케이스에서 직원 1번부터 5번까지의 수열은 다음과 같다.

$S$ : 13, 16, 2, 5, 8
$M$ : 17, 3, 13, 14, 16
상사 번호: $17 \bmod 1 = 0$ , $3 \bmod 2 = 1$ , $13 \bmod 3 = 1$ , $14 \bmod 4 = 2$ , $16 \bmod 5 = 1$

그래서 조직도는 다음과 같다. 마리(0번)의 부하는 1번, 1번의 부하는 2번과 3번과 5번, 2번의 부하는 4번이다. 0번부터 5번까지의 연봉은 각각 10, 13, 16, 2, 5, 8이고 $D = 5$ 다.

최적의 선택은 0번, 1번, 5번을 남기는 것이다. 세 사람의 연봉은 각각 10, 13, 8이다. 예를 들어 2번은 남길 수 없다. 2번의 연봉은 0번의 연봉 10에서 5를 넘게 떨어져 있는데 0번은 내보낼 수 없으므로, 2번과 2번에게 보고하는 직원은 모두 내보내야 한다.