#include <iostream>

using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return d;
}
int main()
{
    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==0){
            //得到的解时mk+x中的一个解，可能会溢出，需要mod m
            cout<<(long long )x*b/d%m<<endl;//将x也扩大b/d倍
        }
        else
            cout<<"impossible"<<endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}