Description

The game rules are as follows: The player gives three integers $A_0$, $a$, $b$, which define a linear recurrence: $A_i=a \times A_{i-1} +b$ It defines an infinite sequence { $A_1$, $A_2$, $A_3$, ... }. The game system randomly generates a number $n$. If $n$ can be represented as the sum of several distinct terms from this sequence (excluding $A_0$), the player wins; otherwise, the player loses. Now Daning has forced the operator to hand over a batch of recent game testdata, but he is too lazy to compute them one by one. Please help determine how many times the player won in the testdata.

Input Format

The first line contains a positive integer $T$, the number of games played. Each of the next $T$ lines contains four integers, describing one game: $A_0$, $a$, $b$, $n$.

Output Format

Output one line with $Ans$, the number of times the player won among the $T$ games.

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

Hint

Sample explanation: In games $1 \sim 3$ the player loses; in games $4 \sim 7$ the player wins.

For all testdata, $1 \leq a \leq 10$, $0 \leq b \leq 10^4$, $0 \leq n \leq 10^9$, $0 \leq A_0 \leq 100$.

In fact, the player's win rate in this game is negligible.

Translated by ChatGPT 5