题目背景

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

题目描述

游戏规则如下：玩家给出 $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$ 场游戏中获胜的次数。

7
3 1 5 16
10 1 0 5
2 1 0 3
2 1 0 10
3 1 5 59
1 2 0 998
0 1 0 0

4

提示

样例说明：

第 $1\sim 3$ 场游戏玩家失败，$4\sim 7$ 场游戏玩家胜利。

事实上这个游戏玩家的胜率微乎其微。