#include <bits/stdc++.h>
#define File(name) freopen(#name".in", "r", stdin); freopen(#name".out", "w", stdout);
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<typename T>
inline T read(){
    T n = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        n = n * 10 + ch - '0';
        ch = getchar();
    }
    return f * n;
}
template<typename T>
void write(T n){
    if(n < 0) return putchar('-'), write(-n);
    if(n / 10) write(n / 10);
    putchar(n % 10 + '0');
}
void input() {}
template<typename Type, typename... Types>
void input(Type &arg, Types &...args){
    arg = read<Type>();
    input(args...);
}
namespace Main{
    const int N = 1005;
    int t, n, m, p; ll f[N][N], binom[N][N], ans;
    void Main(){
        input(t, p);
        binom[0][0] = 1;
        for(int i = 1; i < N; i++){
            binom[i][0] = 1;
            for(int j = 1; j <= i; j++) binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % p;
        }
        while(t--){
            input(n, m);
            ll tot = 1;
            for(int i = 0; i < n; i++) tot = tot * m % p;
            ans = tot;
            for(int k = 1; k < n; k++){
                int lim = n / (k + 1);
                for(int i = 0; i <= n; i++) for(int j = 0; j <= lim + 1; j++) f[i][j] = 0;
                for(int i = 0; i <= lim; i++) f[0][i] = 1;
                for(int i = 1; i <= n; i++){
                    for(int j = 0; j <= lim; j++){
                        f[i][j] = f[i - 1][j] * (m - j) % p;
                        if(i >= k + 1){
                            f[i][j] = (f[i][j] - f[i - k - 1][j + 1] *
                                       binom[i - 1][k] % p * (m - j) % p + p) % p;
                        }
                    }
                }
                ans = (ans + tot - f[n][0] + p) % p;
            }
            write(ans), puts("");
        }
        return;
    }
} // namespace Main
int main(){
#ifdef Liuxizai
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif // Liuxizai
    Main::Main();
    return 0;
}