Darts is a popular sport in Europe. The dartboard is divided into $20$ sectors, labeled with values from $1$ to $20$. Each sector contains single, double, and triple regions; hitting these regions awards the sector's value multiplied by the corresponding multiplier. For example, hitting the triple region of $18$ awards $54$ points. Additionally, in the center of the board, there is an "inner bullseye" and an "outer bullseye," worth $25$ and $50$ points, respectively.

A common rule in darts is that the final throw must land in a double region to win the game. That is, if $12$ points remain, one must hit the double $6$ to win; hitting a single $12$ or a triple $4$ does not count. Specifically, the "outer bullseye" is also considered a double (a double of $25$). Under these rules, the maximum score that can be cleared in $3$ throws is $170$ (two triple $20$s, finishing with an outer bullseye).

Now, lxhgww has changed the values of the $1$ to $20$ sectors to $1$ to $K$, and changed the value of the inner bullseye to $M$ (the outer bullseye is double that value). lxhgww wants to know if it is possible to clear a score of $X$ within $3$ throws (it is not required to use all $3$ throws). Similarly, the final throw must be a double (including the outer bullseye).

Input

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

The second line contains $5$ integers $A_1, B_1, C_1, D_1, K_1$. The first test case has a dartboard with values from $1$ to $K_1$. Subsequent test cases have $K_i$ determined by the formula $K_i = (A_1 K_{i-1}^2 + B_1 K_{i-1} + C) \bmod D_1 + 20$.

The third line contains $5$ integers $A_2, B_2, C_2, D_2, M_1$. The first test case has an inner bullseye value of $M_1$. Subsequent test cases have $M_i$ determined by the formula $M_i = (A_2 M_{i-1}^2 + B_2 M_{i-1} + C) \bmod D_2 + 20$.

The fourth line contains $5$ integers $A_3, B_3, C_3, D_3, X_1$. The first test case has a target score of $X_1$. Subsequent test cases have $X_i$ determined by the formula $X_i = (A_3 X_{i-1}^2 + B_3 X_{i-1} + C_3) \bmod D_3 + 20$.

Output

Output a single integer representing the number of test cases that can be cleared.

Examples

Input 1

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

Output 1

4

Constraints

For $30\%$ of the data, $1 \le T \le 20$, $20 \le K_1, M_1, X_1, D_1, D_2, D_3 \le 10^3$.

For $100\%$ of the data, $1 \le T \le 10^6$, $20 \le K_1, M_1, X_1, D_1, D_2, D_3 \le 10^9$, $0 \le A_1, B_1, A_2, B_2, C_2, A_3, B_3, C_3 \le 10^9$.