#include <iostream>
#include <cstring>
using namespace std;

void solve()
{
    long long M = (int)1e9;
    long long p, q;
    scanf("%I64d%I64d", &q, &p);
    long long m1=M%p, m2=M*M%p;
    long long x=(q-1)%p, y=(q-2)%p;
    if (x%2 == 0) {
        x /= 2;
    } else {
        y /= 2;
    }
    long long a=x/M, b=x%M, c=y/M, d=y%M;
    long long ans = a*c%p*m2%p;
    ans += a*d%p*m1%p;
    ans %= p;
    ans += b*c%p*m1%p;
    ans %= p;
    ans += b*d%p%p;
    ans %= p;
    printf("%I64d\n", ans);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i=0; i<n; ++i) {
        solve();
    }
    return 0;
}