Language: C++

/**
 *    author:  tourist
 *    created: 30.09.2017 15:59:34       
**/
#include <bits/stdc++.h>

using namespace std;

inline void add(int &a, int b, int md) {
  a += b;
  if (a >= md) a -= md;
}

inline void sub(int &a, int b, int md) {
  a -= b;
  if (a < 0) a += md;
}

inline int mul(int a, int b, int md) {
#if !defined(_WIN32) || defined(_WIN64)
  return (long long) a * b % md;
#endif
  unsigned long long x = (long long) a * b;
  unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;
  asm(
    "divl %4; \n\t"
    : "=a" (d), "=d" (m)
    : "d" (xh), "a" (xl), "r" (md)
  );
  return m;
}

inline int power(int a, long long b, int md) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a, md);
    }
    a = mul(a, a, md);
    b >>= 1;
  }
  return res;
}

inline int inv(int a, int md) {
  a %= md;
  if (a < 0) a += md;
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a; swap(a, b);
    u -= t * v; swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += md;
  return u;
}

template<typename T>
T extgcd(T a, T b, T &x, T &y) {
/*  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T p = b / a;
  T g = extgcd(b - p * a, a, y, x);
  x -= p * y;
  return g;*/
  x = 0, y = 1;
  while (a) {
    T t = b / a;
    b -= t * a; swap(a, b);
    u -= t * v; swap(u, v);
  }
  return b;
}

template<typename T>
bool diophantine(T a, T b, T c, T &x, T &y, T &g) {
  if (a == 0 && b == 0) {
    if (c == 0) {
      x = y = g = 0;
      return true;
    }
    return false;
  }
  if (a == 0) {
    if (c % b == 0) {
      x = 0;
      y = c / b;
      g = abs(b);
      return true;
    }
    return false;
  }
  if (b == 0) {
    if (c % a == 0) {
      x = c / a;
      y = 0;
      g = abs(a);
      return true;
    }
    return false;
  }
  g = extgcd(a, b, x, y);
  if (c % g != 0) {
    return false;
  }
  T dx = c / a;
  c -= dx * a;
  T dy = c / b;
  c -= dy * b;
  x = dx + (T) ((__int128) x * (c / g) % b);
  y = dy + (T) ((__int128) y * (c / g) % a);
  g = abs(g);
  return true;
}

int get_phi(int m) {
  int phi = m;
  int tmp = m;
  for (int i = 2; i * i <= tmp; i++) {
    if (tmp % i == 0) {
      phi /= i;
      phi *= (i - 1);
      while (tmp % i == 0) {
        tmp /= i;
      }
    }
  }
  if (tmp > 1) {
    phi /= tmp;
    phi *= tmp - 1;
  }
  return phi;
}

long long solve(int a, int m) {
  if (m == 1) {
    return 30;
  }
  int phi = get_phi(m);
  int g = __gcd(m, phi);
  long long k = solve(a, g);
  int value = power(a, k, m);
  k %= phi;
  // res = value (mod m)
  // res = k (mod phi)
  // res = m * x + value = phi * y + k
  int x, y;
  assert(diophantine(m, -phi, (int) (k - value), x, y, g));
  long long res = (long long) m * x + value;
  while (res < 30) {
    res += (long long) m / g * phi;
  }
  return res;
}

int main() {
  int tt;
  scanf("%d", &tt);
  while (tt--) {
    int a, m;
    scanf("%d %d", &a, &m);
    long long k = solve(a, m);
    cout << k << endl;
    assert(power(a, k, m) == k % m);
  }
  return 0;
}


Compiler output:
a.cc: In function 'T extgcd(T, T, T&, T&)':
a.cc:74:5: error: 'u' was not declared in this scope
   74 |     u -= t * v; swap(u, v);
      |     ^
a.cc:74:14: error: 'v' was not declared in this scope
   74 |     u -= t * v; swap(u, v);
      |              ^