공정국 (작은 입력)

공정국은 회사가 직원을 조직하고 급여를 지급하는 방식을 법으로 엄격하게 정한다.

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 1000$
• $1 \le D \le 1000$
• $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$
• $1 \le R_s, R_m \le 1000$

각 테스트 케이스마다 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$번, $5$번을 남기는 것이다. 세 사람의 연봉은 각각 10, 13, 8이다. 예를 들어 직원 $2$번은 남길 수 없다. 연봉이 16이라 직원 $0$번의 연봉 10과 5보다 더 차이 나는데, 직원 $0$번은 해고할 수 없기 때문이다. 직원 $2$번이 떠나면 그에게 보고하는 직원도 모두 떠난다.