const int N = 2005;
int ans[N][N];
void init() { // 递推预处理
  for (int i = 0;i < N;++i) {
    for (int j = 0;j <= i;++j) {
      if (!j)ans[i][j] = 1;
      else ans[i][j] = (ans[i - 1][j] + ans[i - 1][j - 1]) % mod;
    }
  }
}
int main() {
  init();
  int n;cin >> n;
  while (n--) {
    int a, b;cin >> a >> b;
    printf("%d\n", ans[a][b]);
  }
  return 0;
}

const int N = 100010;
int fact[N], infact[N];
int qmi(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1)res = (LL)res * a % mod;
    a = (LL)a * a % mod;
    b >>= 1;
  }
  return res;
}
int main() {
  fact[0] = infact[0] = 1;
  for (int i = 1;i < N;++i) {
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2) % mod; //求逆元
  }
  int n;cin >> n;
  while (n--) {
    int a, b;
    cin >> a >> b;
    printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
  }
  return 0;
}

const int N = 100010;
int p;
int qmi(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1)res = (LL)res * a % p;
    a = (LL)a * a % p;
    b >>= 1;
  }
  return res;
}
int C(int a, int b) {
  if (b > a)return 0;
  int res = 1;
  for (int i = 1, j = a;i <= b;++i, --j) {
    res = (LL)res * j % p;
    res = (LL)res * qmi(i, p - 2) % p;
  }
  return res;
}
int lucas(LL a, LL b) {
  if (a < p && b < p)return C(a, b);
  return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}
int main() {
  int n;cin >> n;
  while (n--) {
    LL a, b;
    cin >> a >> b >> p;
    cout << lucas(a, b) << endl;
  }
  return 0;
}

const int N = 100010;
bool st[N];
int primes[N], cnt;
int sum[N];
//欧拉筛
void get_primes(int n) {
  for (int i = 2;i <= n;++i) {
    if (!st[i]) {
      primes[cnt++] = i;
    }
    for (int j = 0;primes[j] <= n / i;++j) {
      st[primes[j] * i] = true;
      if (i % primes[j] == 0)break;
    }
  }
}
//求n的阶乘中 质因子p的次数
int get(int n, int p) {
  int res = 0;
  while (n) {
    res += n / p;
    n /= p;
  }
  return res;
}
//高精度乘法
vector<int>mul(vector<int>a, int b) {
  vector<int >c;
  int t = 0;
  for(int i = 0;i < a.size() || t;++i){
    if(i < a.size())t += a[i] * b;
    c.push_back(t % 10);
    t /= 10;
  }
  return c;
}
int main() {
  int a, b;cin >> a >> b;
  get_primes(a);
  for (int i = 0;i < cnt;i++) {
    int p = primes[i];
    sum[i] = get(a,p) - get(b,p) - get(a - b,p);//最终结果中质因子p的次数
  }
  vector<int>ans;
  ans.push_back(1);
//因为数据太大可能会溢出LL 所以不用快速幂 用高精度乘法
  for (int i = 0;i < cnt;++i) {
    for (int j = 0; j < sum[i];++j) {
      ans = mul(ans, primes[i]);//将最终化简结果的质因数分解形式变成原来的数据
    }
  }
  for (int i = ans.size() - 1;i >= 0;--i)printf("%d", ans[i]);
  cout << endl;
  return 0;
}