Gats's Growing Jumps

Time limit: 3000 msMemory limit: 256 MB

Gats starts at position $0$ on an infinite path. Fish stalls are located at every position divisible by $M$ .

His first jump has length $D$ . Every subsequent jump is $B$ times as long as the preceding jump. Therefore, the $i$ -th jump has length $D B^{i-1}$ , and after exactly $L$ jumps Gats is at position

P_L=\sum_{i=0}^{L-1} D B^i.

A jump count $L$ is called successful if Gats is at a fish stall after exactly $L$ jumps; equivalently, $M \mid P_L$ .

For each test case, determine how many successful jump counts $L$ satisfy $1 \le L \le N$ .

Input

The first line contains an integer $T$ ( $1 \le T \le 10$ ), the number of test cases.

Each of the next $T$ lines contains four integers $B$ , $D$ , , and (, , , ).

Output

For each test case, print one integer: the number of successful jump counts $L$ satisfying $1 \le L \le N$ .

Samples

Sample 1

Input

Output

In the first test case, the successful jump counts are $6$ , $12$ , and $18$ . In the second test case, there are no successful jump counts. In the third test case, they are $2$ , $4$ , $6$ , , and . In the final test case, every jump count from through is successful.

Gats's Growing Jumps

Input

Output

Samples

Sample 1

Submit

Submissions