#include <bits/stdc++.h>
using namespace std;
long long powmod(long long base, long long exponent, long long mod) {
  long long ans = 1;
  while (exponent) {
    if (exponent & 1) ans = (ans * base) % mod;
    base = (base * base) % mod;
    exponent /= 2;
  }
  return ans;
}
long long gcd(long long a, long long b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
const int upperlimit = 71;
const int mod = 998244353;
long long fact[upperlimit];
long long invfact[upperlimit];
vector<long long> pdv;
void func(long long n) {
  for (int i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) pdv.push_back(i);
    while (n % i == 0) n /= i;
  }
  if (n > 1) pdv.push_back(n);
}
int pw(long long n, long long i) {
  int ans = 0;
  while (n % i == 0) {
    ans++;
    n /= i;
  }
  return ans;
}
int main() {
  fact[0] = 1;
  invfact[0] = 1;
  for (int i = 1; i < upperlimit; i++) {
    fact[i] = fact[i - 1];
    fact[i] *= i;
    fact[i] %= mod;
    invfact[i] = powmod(fact[i], mod - 2, mod);
  }
  long long d, u, v;
  int q;
  long long temp = 1;
  int lol = 0;
  scanf("%lld", &d);
  func(d);
  scanf("%d", &q);
  while (q--) {
    scanf("%lld", &u);
    scanf("%lld", &v);
    long long gc = gcd(u, v);
    temp = 1;
    lol = 0;
    for (int i = 0; i < pdv.size(); i++) {
      int gg = abs(pw(gc, pdv[i]) - pw(u, pdv[i]));
      temp *= invfact[gg];
      temp %= mod;
      lol += gg;
    }
    temp *= fact[lol];
    temp %= mod;
    lol = 0;
    for (int i = 0; i < pdv.size(); i++) {
      int gg = abs(pw(gc, pdv[i]) - pw(v, pdv[i]));
      temp *= invfact[gg];
      temp %= mod;
      lol += gg;
    }
    temp *= fact[lol];
    temp %= mod;
    printf("%lld\n", temp);
  }
  return 0;
}
