题目描述

飞镖是在欧洲颇为流行的一项运动。它的镖盘上分为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^2_{i-1}+B_1K_{i-1}+C_1)mod D_1 + 20$决定，其中第$i(1<i\le T)$组数据的镖盘是从1到$K_i$分的。

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

第四行是5个整数，$A_3,B_3,C_3,D_3,X_1$，表示第一组数据需要解决的分数是$X_1$分的，随后数据的镖盘由公式$X_i=(A_3X^2_{i-1}+B_3X_{i-1}+C_3)mod D_3 + 20$决定，其中第$i(1<i\le T)$组数据需要解决的分数是$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 K1,M1,X1,D1,D2,D3\le 1000$

对于100%的数据，保证$1\le T\le 10^6$,$20\le K1,M1,X1,D1,D2,D3\le 10^9$

对于所有的数据，保证$0\le A1,B1,A2,B2,C2,A3,B3,C3 \le 10^9$