#include <bits/stdc++.h>
const long long mod = 998244353;
long long factor[105];
long long f[105], invf[105];
long long power(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b /= 2;
  }
  return res;
}
long long inv(long long u) { return power(u, mod - 2); }
void preWork(int n) {
  f[0] = invf[0] = 1;
  for (long long i = 1; i <= n; i++) {
    f[i] = f[i - 1] * i % mod;
    invf[i] = inv(f[i]);
  }
}
int main() {
  preWork(100);
  long long d;
  scanf("%lld", &d);
  int n = 0;
  for (long long i = 2; i * i <= d; i++) {
    if (d == 1) break;
    if (d % i == 0) {
      factor[++n] = i;
      while (d % i == 0) d /= i;
    }
  }
  if (d != 1) factor[++n] = d;
  int q;
  scanf("%d", &q);
  while (q--) {
    long long u, v;
    scanf("%lld%lld", &u, &v);
    int countP = 0, countN = 0;
    long long divisor = 1;
    for (int i = 1; i <= n; i++) {
      if (u == 1 && v == 1) break;
      long long counta = 0, countb = 0;
      while (u % factor[i] == 0) {
        counta++;
        u /= factor[i];
      }
      while (v % factor[i] == 0) {
        countb++;
        v /= factor[i];
      }
      if (counta != countb) {
        long long diff = counta - countb;
        if (diff > 0) {
          countP += diff;
          divisor = divisor * invf[diff] % mod;
        } else {
          diff *= -1;
          countN += diff;
          divisor = divisor * invf[diff] % mod;
        }
      }
    }
    long long ans = divisor;
    ans = ans * f[countP] % mod;
    ans = ans * f[countN] % mod;
    printf("%lld\n", ans);
  }
  return 0;
}
