P3996 失败的竞猜游戏

大宁是一个喜欢赌博的人，最近在玩一款竞猜游戏，然而屡战屡败。大宁非常不高兴，就去找游戏的运营商理论，质疑游戏的数据是否有意针对玩家。

游戏规则如下：玩家给出 $A_0$，$a$，$b$ 三个整数，代表一个线性递推式： $A_i=a \times A_{i-1} +b$ 它定义了一个无限长度的数列 {$A_1$，$A_2$，$A_3$……}，而游戏系统会随机生成一个数 $n$，如果 $n$ 可以表示为该数列中的若干个**互不相同**的项 ( $A_0$ 不计入数列中) 之和，那么玩家胜利，反之玩家失败。现在大宁通过逼迫运营商交出了一组最近的游戏数据，但是他懒得一个个去算了，现在请你帮忙计算一下，数据中玩家一共获胜了多少次。

第一行一个正整数 $T$，表示进行了 $T$ 场游戏。 接下来 $T$ 行，每行四个整数，描述一场游戏，分别为题目中的 $A_0$，$a$，$b$，$n$。

输出一行 $Ans$，表示玩家在 $T$ 场游戏中获胜的次数。

样例说明： 第 $1\sim 3$ 场游戏玩家失败，$4\sim 7$ 场游戏玩家胜利。 | 测试点编号 | 数据范围 | 特殊性质 | | :----------: | :----------: | :----------: | | $1\sim 2$ | $T=10$, $n\leq 10^3$ | $a=1$ | | $3\sim 4$ | $T=10^3$, $n\leq 10^4$ | $a=2$ | | $5$ | $T=10^4$, $n\leq 10^9$ | $a\leq 3$ | | $6$ | $T=10^5$, $n\leq 10^9$ | $b=0$ | | $7\sim 10$ | $T=2\times 10^5$, $n\leq10^9$ | 无 | 对于所有数据，$1\leq a\leq10$, $0 \leq b \leq 10^4$, $0\leq n \leq 10^9$, $0 \leq A_0 \leq 100$。 事实上这个游戏玩家的胜率微乎其微。