from sys import stdin, stdout
def input_reader():
    for token in stdin.read().split(): yield token
next_token = input_reader().next

T = int(next_token())
for t in range(T):
    a, b, c, N = [ int(next_token()) for i in range(4) ]
    answer = [ None ]*N
    in_stack = [ None ]*N
    something_points_here = [ False ]*N
    for n in range(N):
        something_points_here[ (a*n*n+b*n+c)%N ] = True
    for n in range(N):
        if answer[n] is None:
            stack = [n]
            in_stack[n] = 0
            while True:
                nextn = (a*stack[-1]*stack[-1] + b*stack[-1] + c)%N
                if answer[nextn] is None:
                    if in_stack[nextn] is None:
                        in_stack[nextn] = len(stack)
                        stack.append(nextn)
                    else:
                        cycle_length = len(stack) - in_stack[nextn]
                        for i in range(len(stack)):
                            answer[ stack[i] ] = max( cycle_length, len(stack)-i )
                            in_stack[ stack[i] ] = None
                        break
                else:
                    for i in range(len(stack)):
                        answer[ stack[i] ] = answer[nextn] + len(stack) - i
                        in_stack[ stack[i] ] = None
                    break
    print(max(answer))