Fairland (Large)

Fairland regulates how companies organize and pay their employees with these laws.

1. Each company has exactly one CEO, and the CEO has no manager.
2. Every employee other than the CEO has exactly one manager. The org chart of a company is therefore a tree with no cycles.
3. While an employee works for the company, that employee's manager never changes. If a manager leaves, every employee reporting to that manager must leave as well.
4. The CEO never leaves the company.
5. Every employee receives a salary, an amount of Fairland dollars per year. An employee's salary never changes.
6. Different employees may have different salaries, and a salary has no relation to the employee's position in the org chart.

The government has just passed one more law.

7. The difference between the largest salary and the smallest salary in the whole company must be at most $D$.

Marie is the CEO of Fairland General Stuff Corporation, and she has to make the company comply with the new law. That may require laying off some employees. She knows the list of employees, each employee's manager, and each employee's salary. Find the largest number of employees she can keep, including herself.

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains two space separated integers, the number of employees $N$ and the maximum allowed salary difference $D$. The second line contains four space separated integers $S_0$, $A_s$, $C_s$, $R_s$, and the third line contains four space separated integers $M_0$, $A_m$, $C_m$, $R_m$. These eight integers define two sequences.

$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$

Marie's employee ID is 0, and the other employees have IDs from 1 to $N-1$. The salary of employee $i$ is $S_i$. For every employee $i$ other than Marie, the manager is $M_i \bmod i$. So $M_0$ has nothing to do with Marie's manager. Marie has none.

Limits

• $1 \le T \le 100$
• $1 \le N \le 10^6$, and the sum of $N$ over all test cases is at most $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$

For each test case, print one line in the format Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the largest number of employees Marie can keep, including herself, so that laws 1 through 7 all hold.

In the first test case of the sample input the company has only the CEO and no other employees. It breaks none of the laws, so nobody is laid off.

In the second test case the sequences for employees 1 through 5 are these.

• $S$: 13, 16, 2, 5, 8
• $M$: 17, 3, 13, 14, 16
• Manager numbers: $17 \bmod 1 = 0$, $3 \bmod 2 = 1$, $13 \bmod 3 = 1$, $14 \bmod 4 = 2$, $16 \bmod 5 = 1$

The org chart is therefore this. Marie (employee 0) manages employee 1, employee 1 manages employees 2, 3 and 5, and employee 2 manages employee 4. The salaries of employees 0 through 5 are 10, 13, 16, 2, 5, 8, and $D = 5$.

The best choice keeps employees 0, 1 and 5, whose salaries are 10, 13 and 8. Employee 2, for instance, cannot be kept. Her salary is more than 5 away from employee 0's salary of 10, and employee 0 cannot be laid off, so employee 2 and everyone reporting to her must go.