'''
转换成拓展欧几里得问题求解
'''

def exp_gcd(a, b):
    flag = True
    if a > b:
        flag = False
        a, b = b, a

    if a == 0:
        return (b, 0, 1) if flag else (b, 1, 0)

    gcd_val, x, y = exp_gcd(b%a, a)
    new_x = y - x * (b // a)
    new_y = x
    return (gcd_val, new_x, new_y) if flag else (gcd_val, new_y, new_x)

n = int(input())
for _ in range(n):
    a, b, m = map(int, input().split())
    gcd_val, x, y = exp_gcd(a, m)

    if b % gcd_val != 0:
        print('impossible')
    else:
        print((x * (b // gcd_val)) % m)