Winning the Recursive Sum Game

In this problem, the game rules are defined by a linear recurrence. A player chooses three integers (A_0), (a), and (b). An infinite sequence ({A_i}{i\geq 1}) is then defined by the recurrence: [ A_i = a \times A{i-1} + b, \quad i \ge 1 ] Note that (A_0) is not included in the sequence. After the sequence is defined, the game system randomly generates an integer (n). If (n) can be represented as the sum of some distinct terms from the sequence (each term can be used at most once), then the player wins; otherwise, the player loses.

You are given a dataset containing several games. For each game, you are given the four integers (A_0), (a), (b), and (n). Your task is to determine the total number of games the player won.

Note:

• When \(a = 1\), the recurrence becomes \(A_i = A_{i-1} + b\), i.e. an arithmetic sequence starting from \(A_1 = A_0+b\).
• For each game, you only need to consider the terms of the sequence that do not exceed \(n\) because larger terms cannot contribute to the sum.
• You may assume that all input values are such that the sequence is strictly increasing.

Example

Consider a game with \(A_0=1\), \(a=2\), \(b=1\), and \(n=10\). The sequence is computed as follows: \[ A_1 = 2\times1 + 1 = 3, \quad A_2 = 2\times3+1 = 7, \quad A_3 = 2\times7+1 = 15 \ (>10) \] Since \(10 = 7 + 3\) (using distinct terms \(A_2\) and \(A_1\)), the player wins this game.

inputFormat

The first line contains a single integer (T) ((1 \le T \le 10^5)), the number of games. Each of the next (T) lines contains four integers: (A_0), (a), (b), and (n). All values are separated by spaces.

outputFormat

Output a single integer representing the total number of games the player won.

sample

3
1 2 1 8
1 2 1 10
3 1 3 12

2