#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
long long fun(long long s,long long M)
{
//s*(1+s)*(1+2*s)*(-1+3*s+3*s^2)/30
// s= 30t + y
ll sM,c2,c3,c90,c6;
ll y = s%30 , sM = s%M ,c2=2 , c3=3,c90=90, c6=6;
ll t = ((s-y)/30)%M;
ll last = ( c3*sM*sM + c3*sM -1 )%M;
ll last_two = ((c2*sM + 1) * last )%M;
return (t*(sM+1)*last_two + t*y*last_two + c2*t*y*(y+1)*last + y*(y+1)*(c2*y+1)*(c90*t*t + c6*t*y + c3*t) + (y*(y+1)*(c2*y+1)*(c3*y*y+c3*y-1))/30 )%M;
}
int main() {
long long t,n,m,i,s,x,y,ans;
scanf("%lld",&t);
while(t--)
{ans=0;
scanf("%lld",&n,&m);
s=sqrt(n);
for(i=1;i<=s;i++)
{
ans=(ans+((i*i*i)%m)*((i*(n/i))%m))%m;
}
for(i=n/s;i>1;i--)
{
x=n/i;
y=n/(i-1);
ans=(ans+(i-1)*(fun(y,m)-fun(x,m)))%m;
}
if(ans<0)
ans+=m;
printf("%lld\n",ans);
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKbG9uZyBsb25nIGZ1bihsb25nIGxvbmcgcyxsb25nIGxvbmcgTSkKewoJLy9zKigxK3MpKigxKzIqcykqKC0xKzMqcyszKnNeMikvMzAKCS8vIHM9IDMwdCArIHkKCWxsIHNNLGMyLGMzLGM5MCxjNjsKCWxsIHkgPSBzJTMwICwgc00gPSBzJU0gLGMyPTIgLCBjMz0zLGM5MD05MCwgYzY9NjsKCWxsIHQgPSAoKHMteSkvMzApJU07CglsbCBsYXN0ID0gKCBjMypzTSpzTSArIGMzKnNNIC0xICklTTsKCWxsIGxhc3RfdHdvID0gKChjMipzTSArIDEpICogbGFzdCApJU07CglyZXR1cm4gKHQqKHNNKzEpKmxhc3RfdHdvICArIHQqeSpsYXN0X3R3byArIGMyKnQqeSooeSsxKSpsYXN0ICsgeSooeSsxKSooYzIqeSsxKSooYzkwKnQqdCArIGM2KnQqeSArIGMzKnQpICsgKHkqKHkrMSkqKGMyKnkrMSkqKGMzKnkqeStjMyp5LTEpKS8zMCAgKSVNOwp9CgoKCgoKCmludCBtYWluKCkgewoJCglsb25nIGxvbmcgdCxuLG0saSxzLHgseSxhbnM7CglzY2FuZigiJWxsZCIsJnQpOwoJd2hpbGUodC0tKQoJe2Fucz0wOwoJCXNjYW5mKCIlbGxkIiwmbiwmbSk7CgkJcz1zcXJ0KG4pOwoJCQoJCWZvcihpPTE7aTw9cztpKyspCgkJewoJCWFucz0oYW5zKygoaSppKmkpJW0pKigoaSoobi9pKSklbSkpJW07CgkJfQoJCWZvcihpPW4vcztpPjE7aS0tKQoJCXsKCQkJeD1uL2k7CgkJCXk9bi8oaS0xKTsKCQkJYW5zPShhbnMrKGktMSkqKGZ1bih5LG0pLWZ1bih4LG0pKSklbTsKCQl9CgkJCgkJaWYoYW5zPDApCgkJYW5zKz1tOwoJCQoJCXByaW50ZigiJWxsZFxuIixhbnMpOwoJCQoJfQoJCgkKCQoJcmV0dXJuIDA7CgkJCgl9CgkKCQ==
prog.cpp: In function ‘long long int fun(long long int, long long int)’:
prog.cpp:10:16: error: redeclaration of ‘ll sM’
ll y = s%30 , sM = s%M ,c2=2 , c3=3,c90=90, c6=6;
^
prog.cpp:9:5: error: ‘ll sM’ previously declared here
ll sM,c2,c3,c90,c6;
^
prog.cpp:10:26: error: redeclaration of ‘ll c2’
ll y = s%30 , sM = s%M ,c2=2 , c3=3,c90=90, c6=6;
^
prog.cpp:9:8: error: ‘ll c2’ previously declared here
ll sM,c2,c3,c90,c6;
^
prog.cpp:10:33: error: redeclaration of ‘ll c3’
ll y = s%30 , sM = s%M ,c2=2 , c3=3,c90=90, c6=6;
^
prog.cpp:9:11: error: ‘ll c3’ previously declared here
ll sM,c2,c3,c90,c6;
^
prog.cpp:10:38: error: redeclaration of ‘ll c90’
ll y = s%30 , sM = s%M ,c2=2 , c3=3,c90=90, c6=6;
^
prog.cpp:9:14: error: ‘ll c90’ previously declared here
ll sM,c2,c3,c90,c6;
^
prog.cpp:10:46: error: redeclaration of ‘ll c6’
ll y = s%30 , sM = s%M ,c2=2 , c3=3,c90=90, c6=6;
^
prog.cpp:9:18: error: ‘ll c6’ previously declared here
ll sM,c2,c3,c90,c6;
^
prog.cpp: In function ‘int main()’:
prog.cpp:28:21: warning: too many arguments for format [-Wformat-extra-args]
scanf("%lld",&n,&m);
^