测试数据来自 AOCode/1054

P1054 Coding for Codes

Problem Statement

AO's npy made a program.

#include <stdio.h>
int main() {
    unsigned long long x, a, b, c, g=0;
    scanf("%llu%llu%llu%llu", &a, &b, &c, &x);
    while(x<=c) {
        x*=a;
        x+=b;
        g++;
    }
    printf("%llu\n", g);
    return 0;
}

Now she has inputted \(a\), \(b\), \(c\). She wants to output \(g\). She asked AO "If I want to output \(g\), how many different \(x\)s can I choose?

There are multiple test cases.

Input

The first line contains an integer \(t\), the number of test cases.
For each test case, there're four integers \(a\), \(b\), \(c\), \(g\).

Output

Print the number of \(x\)s AO's npy can choose in a line.
If the number is not a finite number, print Inf.

Samples

Input 1

1
2 3 20 2

Output 1

6

In this case, \(x=3,4,5,6,7,8\).

Constraints

• \(1 \le t \le 10^4\)
• \(1 \le a \le 10\)
• \(1 \le b \le 10^9\)
• \(1 \le c \le 10^{15}\)
• \(0 \le g \le 10^2\)

Source?

Times Maths Newspaper (bushi