#include <stdio.h>
#include <math.h>
unsigned long long int flr(long long int n, long long int i,long long int m)
{
    unsigned long long int val = n /i ;
    unsigned long long int t = val % m ;
    return t;
 
}
 
 
 
int main ()
{
 
    unsigned long long int ans ,tot=2,k,n,m,i ;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%llu %llu",&n,&m);
        ans  = 1 * flr(n,1,m);
        for(i=2;i<=n;i++)
        {
        	k = i% m;
            ans =( (ans)%m + (((((k*k)%m*i)%m*i)%m)*(flr(n,i,m))%m )%m);tot++;
        }
        printf("%llu\n",ans);
    }
 
 
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxtYXRoLmg+CnVuc2lnbmVkIGxvbmcgbG9uZyBpbnQgZmxyKGxvbmcgbG9uZyBpbnQgbiwgbG9uZyBsb25nIGludCBpLGxvbmcgbG9uZyBpbnQgbSkKewogICAgdW5zaWduZWQgbG9uZyBsb25nIGludCB2YWwgPSBuIC9pIDsKICAgIHVuc2lnbmVkIGxvbmcgbG9uZyBpbnQgdCA9IHZhbCAlIG0gOwogICAgcmV0dXJuIHQ7Cgp9CgoKCmludCBtYWluICgpCnsKCiAgICB1bnNpZ25lZCBsb25nIGxvbmcgaW50IGFucyAsdG90PTIsayxuLG0saSA7CiAgICBpbnQgdDsKICAgIHNjYW5mKCIlZCIsJnQpOwogICAgd2hpbGUodC0tKQogICAgewogICAgICAgIHNjYW5mKCIlbGx1ICVsbHUiLCZuLCZtKTsKICAgICAgICBhbnMgID0gMSAqIGZscihuLDEsbSk7CiAgICAgICAgZm9yKGk9MjtpPD1uO2krKykKICAgICAgICB7CiAgICAgICAgCWsgPSBpJSBtOwogICAgICAgICAgICBhbnMgPSggKGFucyklbSArICgoKCgoayprKSVtKmkpJW0qaSklbSkqKGZscihuLGksbSkpJW0gKSVtKTt0b3QrKzsKICAgICAgICB9CiAgICAgICAgcHJpbnRmKCIlbGx1XG4iLGFucyk7CiAgICB9CgoKfQo=

MQo0IDEwMDA=

1
4 1000