#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

// a*x+b*y=gcd(a, b)
int exgcd(int a, int b, int &x, int &y){
    if(!b){x=1; y=0; return a;}
    int d=exgcd(b, a%b, y, x);
    y-=a/b*x;
    return d;
}

int main(){
    // 扩展欧几里得算法法求解
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    int n;
    cin>>n;
    while(n--){
        int a, b, m;
        cin>>a>>b>>m;
        int x, y;
        int d=exgcd(a, m, x, y);
        if(b%d) puts("impossible");
        else cout<<(LL)x*(b/d)%m<<endl;
    }

    return 0;
}