Fairland (Small)

Fairland has strict laws about how a company organizes and pays its employees.

1. Every 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 in 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 of Fairland 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$ Fairland dollars.

Marie is the CEO of Fairland General Stuff Corporation, and she has to make the company comply with the new law. That may mean laying off some employees. She knows the list of employees, the manager of each employee, and every salary. Find the largest number of employees she can keep, counting 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 largest 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$. This means $M_0$ does not decide Marie's manager. Marie has none.

Limits

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

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

In the first test case the company has only the CEO and no other employee. No law is broken, 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 best choice is to keep employees $0$, $1$, and $5$, whose salaries are 10, 13, and 8. Employee $2$ cannot be kept, for example: her salary of 16 is more than 5 away from employee $0$'s salary of 10, and employee $0$ cannot be laid off. When employee $2$ leaves, every employee reporting to her leaves too.