#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std; 

inline long long multi(long long x,long long y,long long mod)
{
long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
return tmp<0 ? tmp+mod : tmp;
}
long long n,m;
int main()
{
      int T;
     scanf("%d",&T);
     for (;T--;)
    { 
     scanf("%lld%lld",&n,&m);
     if (n<=2) puts("0");
     else 
     {
           if (n&1) printf("%lld\n",multi((n-1)/2,n-2,m));
           else printf("%lld\n",multi((n-2)/2,n-1,m));
     }
   }
}