Взлом RSA

#include <iostream>
#include <cmath>
using namespace std;
long long gcd (long long a, long long b, long long & x, long long & y) {
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    long long x1, y1;
    long long d = gcd (b%a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

long long phi (long long n) {
    long long result = n;
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    if (n > 1)
        result -= result / n;
    return result;
}
long long binpow (long long a, long long n, long long m) {
    long long res = 1;
    while (n) {
        if (n & 1)
            {
        res *= a;
        res%=m;
      }
        a *= a;
    a%=m;
        n >>= 1;
    }
    return res;
}

int main() {
  long long p;
  cin >> p;
  for(int i=1;i<=p;i++)
  {
  long long e, n, c;
  cin >> e >> n >> c;
  long long x, y;
  long long m=phi(n);
  long long  a= gcd(e,m,x,y);
  x = (x % m + m) % m;
  cout << binpow(c,x, n) << endl;
  }
}