#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
// ax + my =b
//只要满足 b是d的倍数就行.

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()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b,m;
        scanf("%d%d%d",&a,&b,&m);
        int x,y;
        int d=exgcd(a,m,x,y);
        if(b % d) cout<<"impossible"<<endl;
        else printf("%d\n",(LL)b / d * x % m);
    }
    return 0;
}

#include<iostream>
#include<algorithm>

using namespace std;

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;
}

//  x'=x,y'=y
// y'-= a / b * x

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int x,y;
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;

LL qmi(int a, int b, int p)
{
    LL res=1%p;
    while(b)
    {
        if(b & 1) res = res * a %p;
        a = a * (LL) a % p;
        b>>=1;
    }
    return res;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,p;
        scanf("%d%d",&a,&p);
        if(a % p == 0) cout<<"impossible"<<endl;
        else cout<<qmi(a,p-2,p)<<endl;
    }
    return 0;
}

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

LL qmi(int a, int b, int p)
{
    LL res=1 % p;
    while(b)
    {
        if(b & 1) res=res * a % p;
        a = a *(LL) a % p;
        b>>=1;
    }
    return res;
}


int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b,p;
        scanf("%d%d%d",&a,&b,&p);

        printf("%lld\n",qmi(a,b,p));
    }
    return 0;
}

#include<iostream>

using namespace std;

typedef long long LL;

const int N=1000010;

int primes[N],cnt;
int euler[N];
bool st[N];

void get_eulers(int n)
{
   euler[1]=1;
   for(int i=2;i<=n;++i)
   {
       if(!st[i])
       {
           primes[cnt++]=i;
           euler[i]=i-1;
       }
       for(int j=0;primes[j]<=n/i;++j)
       {
          int t=primes[j] * i;
            st[t]=true;
           if(i % primes[j] == 0)
           {
               euler[t]=euler[i] * primes[j];
               break;
           }
           euler[t]=(primes[j]-1) * euler[i];
       }
   }
}

int main()
{
    int n;
    cin>>n;
    get_eulers(n);
    LL res = 0;
    for(int i=1;i<=n;++i) res+=euler[i];
    cout<<res<<endl;
    return 0;
}

#include<iostream>
using namespace std;

int phi(int x)
{
    int res=x;
    for(int i=2;i<=x/i;++i)
    {
        if(x % i == 0)
        {
            res = res / i * (i - 1); // 45 *(1 - 1/3) = 15
            while(x % i == 0) x/=i;
        }
    }
    // 30 / 5 * 4
       if(x>1) res = res / x *(x - 1); 
        return res;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        cout<<phi(x)<<endl;
    }
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;

int gcd(int a, int b)
{
    return b?gcd(b,a % b):a;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>

using namespace std;
typedef long long LL;

const int N=110, mod = 1e9 + 7;

int main()
{
   int n;
   cin>>n;
   unordered_map<int,int> primes;
   while(n--)
   {
       int x;
       cin>>x;
       for(int i=2;i<=x/i;++i)
       {
           while(x % i == 0)
           {
               x/=i;
               primes[i]++;
           }
       }
       if(x>1) primes[x]++;
   }
   LL res=1;
   for(auto p: primes)
   {
       LL t=1;
       int a=p.first,b=p.second;
       while(b--) t=(t * a + 1) % mod;
       res = res * t % mod;
   }
   cout<<res<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<int> get_divisors(int x)
{
    vector<int> res;
    for(int i=1;i<=x/i;++i)
    {
        if(x % i == 0)
        {
            res.push_back(i);
            if(i != x/i) res.push_back(x/i);
        }
    }
    sort(res.begin(),res.end());
    return res;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        auto res=get_divisors(x);
        for(auto x: res) cout<<x<<' ';
        cout<<endl;
    }
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000010;
int prime[N],cnt;
bool st[N];
//埃式筛法
void get_primes(int n)
{
    for(int i=2;i<=n;++i)
    {
        if(st[i]) continue;
        prime[cnt++]=i;
        for(int j=i+i;j<=n;j+=i)
        {
            st[j]=true;
        }
    }
}

int main()
{
    int n;
    cin>>n;
    get_primes(n);

    cout<<cnt<<endl;
    return 0;
}