페어랜드 (라지)

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

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

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

7. 회사 전체에서 가장 높은 연봉과 가장 낮은 연봉의 차이는 $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번에게 보고하는 직원은 모두 내보내야 한다.