페어랜드

페어랜드에는 회사가 직원을 조직하고 급여를 지급하는 방식을 규정하는 매우 엄격한 법률이 있다.

• 각 회사에는 관리자가 없는 CEO가 정확히 한 명 있어야 한다.

• CEO를 제외한 모든 직원에게는 정확히 한 명의 관리자가 있어야 한다. (이는 회사의 모든 직원을 나타내는 조직도가 순환이 없는 트리라는 뜻이다.)

• 직원이 회사에서 근무하는 동안에는 그 직원의 관리자가 절대로 바뀌어서는 안 된다. 이는 관리자가 퇴사하면 그 관리자에게 보고하는 모든 직원도 퇴사해야 한다는 뜻이다.

• CEO는 절대로 회사를 떠나서는 안 된다.

• 모든 직원은 연간 일정액의 페어랜드 달러를 급여로 받는다. 직원의 급여는 절대로 바뀌어서는 안 된다.

• 서로 다른 직원의 급여는 다를 수 있으며, 직원의 급여가 조직도에서 그 직원이 위치한 곳과 반드시 관련되어 있는 것은 아니다.

페어랜드 정부는 방금 다음과 같은 법률을 하나 더 통과시켰다.

• 회사 전체에서 가장 높은 급여와 가장 낮은 급여의 차이는 최대 D Fairland달러여야 한다.

Marie는 Fairland General Stuff Corporation의 CEO이며, 자신의 회사가 새 법률을 준수하도록 해야 한다. 이를 위해 일부 직원을 해고해야 할 수도 있다. Marie에게는 회사 직원과 그들의 관리자 및 급여 목록이 있다. Marie 자신을 포함하여 유지할 수 있는 직원 수의 최댓값은 얼마인가?

제한

메모리 제한: 1 GB.

1 ≤ T ≤ 100. 0 ≤ $S_{0}$ < $R_{s}$. 0 ≤ $M_{0}$ < $R_{m}$. 0 ≤ $A_{s}$, $A_{m}$ ≤ 1000. 0 ≤ $C_{s}$, $C_{m}$ ≤ $10^{9}$.

작은 데이터 세트

시간 제한: 240초. 1 ≤ N ≤ 1000. 1 ≤ D ≤ 1000. 1 ≤ $R_{s}$, $R_{m}$ ≤ 1000.

큰 데이터 세트

시간 제한: 480초. 1 ≤ N ≤ $10^{6}$. 1 ≤ D ≤ $10^{6}$. 1 ≤ $R_{s}$, $R_{m}$ ≤ $10^{6}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 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}$ * $A_{s}$ + $C_{s}$) mod $R_{s}$

• $M_{i+1}$ = ($M_{i}$ * $A_{m}$ + $C_{m}$) mod $R_{m}$

Marie의 직원 ID는 0이며, 다른 모든 직원의 ID는 1부터 N - 1까지이며 양 끝값을 포함한다. 직원 i의 급여는 $S_{i}$이다. Marie가 아닌 모든 직원 i의 관리자는 $M_{i}$ mod i이다. (이는 $M_{0}$가 Marie의 관리자에게 영향을 주지 않는다는 뜻임에 유의하라. Marie에게는 관리자가 없다!)

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 Marie 자신을 포함하여 회사에 유지할 수 있으면서 모든 법률 1-7을 준수하게 되는 직원 수의 최댓값이다.

케이스 #1에서 회사에는 CEO만 있고 다른 직원은 없지만, 어떤 법률도 위반하지 않으므로 변경할 필요가 없다.

케이스 #2의 조직도는 다음과 같다.

최적의 전략은 직원 0, 1, 5을 유지하는 것이다(각각의 급여는 10, 13, 8이다). 예를 들어 직원 2의 급여는 직원 0의 급여인 10에서 5보다 더 많이 차이 나므로 그 직원을 유지할 수 없다. 직원 0은 해고할 수 없으므로 직원 2은 자신에게 보고하는 모든 직원과 함께 해고되어야 한다.

직원 1부터 5까지의 수열을 확인하고 싶다면 다음과 같다.

S: 13, 16, 2, 5, 8 M: 17, 3, 13, 14, 16 관리자 번호: 17 % 1 = 0, 3 % 2 = 1, 13 % 3 = 1, 14 % 4 = 2, 16 % 5 = 1