Comet OJ

C1196 [SCOI2011]飞镖

内存限制：256 MB 时间限制：1000 ms

题目描述

飞镖是在欧洲颇为流行的一项运动。它的镖盘上分为 $20$ 个扇形区域，分别标有 $1$ 到 $20$ 的分值，每个区域中有单倍、双倍和三倍的区域，打中对应的区域会得到分值乘以倍数所对应的分数。例如打中 $18$ 分里面的三倍区域，就会得到 $54$ 分。另外，在镖盘的中央，还有"小红心"和"大红心"，分别是 $25$ 分和 $50$ 分。

通常的飞镖规则还有一条，那就是在最后一镖的时候，必须以双倍结束战斗，才算获胜。也就是说，当还剩 $12$ 分的时候，必须打中双倍的 $6$ 才算赢，而打中单倍的 $12$ 或者三倍的 $4$ 则不算。特别的，"大红心"也算双倍（双倍的 $25$）。在这样的规则下，$3$ 镖能解决的最多分数是 $170$ 分（两个三倍的 $20$，最后用大红心结束）。

现在， lxhgww 把原来的 $1$ 到 $20$ 分的分值变为了 $1$ 到 $K$ 分，同时把小红心的分数变为了 $M$ 分（大红心是其双倍），现在 lxhgww 想知道能否在 $3$ 镖内（可以不一定用满 $3$ 镖）解决 $X$ 分。同样的，最后一镖必须是双倍（包括大红心）。

输入格式

输入的第一行是一个整数 $T$，表示包含了 $T$ 组数据。

第二行是 $5$ 个整数 $A_1 , B_1 , C_1 , D_1 , K_1$。表示第一组数据的镖盘是从 $1$ 到 $K_1$ 分的，随后数据的镖盘由公式 $K_i=(A_1K_{i-1}^2+B_1K_{i-1}+C) \mod D_1 +20$ 决定，其中第 $i$ 组数据需要解决的分数是 $K_i$ 分。

第三行是 $5$ 个正数 $A_2 , B_2 , C_2 , D_2 , M_1$ 表示第一组数据的小红心是 $M_1$ 分，随后数据的镖盘由公式 $K_i=(A_2K_{i-1}^2+B_2K_{i-1}+C) \mod D_2 +20$ 决定，其中第 $i$ 组数据的小红心是 $M_i$ 分。

第四行是 $5$ 个正数 $A_3 , B_3 , C_3 , D_3 , X_1$ 表示第一组数据需要解决的分数是 $X_1$ 分，随后数据的镖盘由公式 $K_i=(A_3K_{i-1}^2+B_3K_{i-1}+C) \mod D_3 +20$ 决定，其中第 $i$ 组数据需要解决的分数是 $X_i$ 分。

输出

输入一行，包括一个数字，表示这 $T$ 组数据中，能够被解决的数据数目。

样例

样例输入 1

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

样例输出 1

4

提示

对于 $30\%$ 的数据，保证 $1 \le T \le 20,20\le K_1,M_1,X_1,D_1,D_2,D_3 \le 10^3$。

对于 $100\%$ 的数据，保证 $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$。