求解线性同余方程

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

typedef long long LL;
int n,d,a,m,x,y,b;

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

int main(){
    cin>>n;
    while(n--){
        scanf("%d%d%d",&a,&b,&m);
        x=y=0;
        d=exgcd(a,m,x,y);
        if(b%d) puts("impossible");
        else printf("%d\n",1LL*x*(b/d)%m);
    }
    return 0;
}