#2440. 「SCOI2011」飞镖

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

飞镖是在欧洲颇为流行的一项运动。它的镖盘上分为 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 组数据中,能够被解决的数据数目。

样例

样例输入

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

样例输出

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