#include <cstdio>

typedef long long ll;

ll p, q, x, y;

ll mod_mul(ll x,ll y,ll n) {
    if (x==0 || y==0) return 0;
    return (((x&1)*y)%n+(mod_mul(x>>1,y,n)<<1)%n)%n;
}

int main() {
    int T;
    for(scanf("%d", &T); T --; ) {
        scanf("%I64d %I64d\n", &q, &p);
        if(q == 2) puts("0");
        else printf("%I64d\n", mod_mul((q - 2), (q - 1) / 2, p));
    }
    return 0;
}