Description

Darts is a popular sport in Europe. The dartboard is divided into 20 sector areas labeled 1 to 20. Each sector has single, double, and triple rings; hitting a ring yields the sector value multiplied by the corresponding multiplier.

For example, hitting the triple ring of 18 scores 54 points.

In addition, at the center of the board there are the outer bull and the inner bull, worth 25 and 50 points respectively.

A common darts rule is that you must finish on a double with your last dart to win. That is, if 12 points remain, you must hit double 6 to win; hitting single 12 or triple 4 does not count.

In particular, the inner bull also counts as a double (double 25). Under these rules, the maximum score that can be finished in 3 darts is 170 (two triple 20s and finishing on the inner bull).

Now, lxhgww changes the sector values from 1–20 to 1–$K$, and changes the outer bull to be worth $M$ points (the inner bull is twice that). lxhgww wants to know whether a total of $X$ points can be finished within 3 darts (you may use fewer than 3 darts). Likewise, the last dart must be a double (including the inner bull).

Input Format

The first line contains an integer $T$, the number of test cases.

The second line contains 5 integers $A_1,B_1,C_1,D_1,K_1$, indicating that in the first test case the board has sectors from 1 to $K_1$. For subsequent test cases, the board parameter is determined by $K_i=(A_1K^2_{i-1}+B_1K_{i-1}+C_1)mod D_1 + 20$, and in the $i$-th test case ($1<i\le T$) the board has sectors from 1 to $K_i$.

The third line contains 5 integers $A_2,B_2,C_2,D_2,M_1$, indicating that in the first test case the outer bull is worth $M_1$ points. For subsequent test cases, the value is determined by $M_i=(A_2M^2_{i-1}+B_2M_{i-1}+C_2)mod D_2 + 20$, and in the $i$-th test case ($1<i\le T$) the outer bull is worth $M_i$ points.

The fourth line contains 5 integers $A_3,B_3,C_3,D_3,X_1$, indicating that in the first test case the required total is $X_1$ points. For subsequent test cases, the target is determined by $X_i=(A_3X^2_{i-1}+B_3X_{i-1}+C_3)mod D_3 + 20$, and in the $i$-th test case ($1<i\le T$) the required total is $X_i$ points.

Output Format

Output one line containing a single integer, the number of test cases among the $T$ that are solvable.

5
1 2 2 10 20
1 3 2 15 25
2 2 5 200 170

4

Hint

For 30% of the testdata, it is guaranteed that $1 \le T \le 20$, $20 \le K_1,M_1,X_1,D_1,D_2,D_3 \le 1000$.

For 100% of the testdata, it is guaranteed that $1 \le T \le 10^6$, $20 \le K_1,M_1,X_1,D_1,D_2,D_3 \le 10^9$.

For all testdata, it is guaranteed that $0 \le A_1,B_1,A_2,B_2,C_2,A_3,B_3,C_3 \le 10^9$.

Translated by ChatGPT 5