#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctype.h>
#include<cmath>
#include<vector>
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#define pi pair<int,int>
#define ppi pair<int,pair<int,int> >
#define pip pair<pair<int,int>,int>
#define pipi pair<pair<int,int>,pair<int,int> >
#define vi vector<int>
#define vc vector<char>
#define vll vector<ll>
#define mp make_pair
#define Min(a,b)((a<b)?a:b)
#define Max(a,b)((a>b)?a:b)
#define Swap(a,b)(a=b+a-(b=a))
#define sfd(d) scanf("%d",&d)
#define sfld(d) scanf("%lld",&d)
#define sff(d) scanf("%f",&d)
#define sfc(ch) scanf("%c",&ch)
#define sfs(s) scanf("%s",s)
#define pfd(d) printf("%d",d)
#define pfld(d) printf("%lld",d)
#define el putchar('\n')
#define sp putchar(' ')
#define Fill(a,val) memset(a,val,sizeof a)
#define pb push_back
#define ppb pop_back
#define INF 123456789
#define mod 1000000007
#define ll long long int
#define si short int
#define gcd __gcd
#define all(a) a.begin(),a.end()
#define T(x) strtok(x, " \n\r\t")
using namespace std;
ll F(ll n){
	return n*(2*n+1)*(n+1)*(3*n*(n+1)-1)/30;
}
ll f(ll n,ll m){
        ll cur = 0,x = n,res = 0,k = 1;
        while (1){
               x = n/k;
               res = (res + F(x)*(n/x - cur))%m;
               if (x == 1)
                       break;
               cur = n/x;
               k = max(k + 1 , n / (x-1));
        }
        return res;
}
int main() {
    int t;sfd(t);
    while(t--) {
        for(int i=0;i<t;++i){
            ll n,m;
            sfld(n);
            sfld(m);
            pfld(f(n,m));el;
        }
    }
    return 0;
}
 

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdGRpbz4KI2luY2x1ZGU8Y3N0cmluZz4KI2luY2x1ZGU8Y3R5cGUuaD4KI2luY2x1ZGU8Y21hdGg+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8bWFwPgojaW5jbHVkZTxsaXN0PgojaW5jbHVkZTxzdGFjaz4KI2luY2x1ZGU8cXVldWU+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2RlZmluZSBwaSBwYWlyPGludCxpbnQ+CiNkZWZpbmUgcHBpIHBhaXI8aW50LHBhaXI8aW50LGludD4gPgojZGVmaW5lIHBpcCBwYWlyPHBhaXI8aW50LGludD4saW50PgojZGVmaW5lIHBpcGkgcGFpcjxwYWlyPGludCxpbnQ+LHBhaXI8aW50LGludD4gPgojZGVmaW5lIHZpIHZlY3RvcjxpbnQ+CiNkZWZpbmUgdmMgdmVjdG9yPGNoYXI+CiNkZWZpbmUgdmxsIHZlY3RvcjxsbD4KI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBNaW4oYSxiKSgoYTxiKT9hOmIpCiNkZWZpbmUgTWF4KGEsYikoKGE+Yik/YTpiKQojZGVmaW5lIFN3YXAoYSxiKShhPWIrYS0oYj1hKSkKI2RlZmluZSBzZmQoZCkgc2NhbmYoIiVkIiwmZCkKI2RlZmluZSBzZmxkKGQpIHNjYW5mKCIlbGxkIiwmZCkKI2RlZmluZSBzZmYoZCkgc2NhbmYoIiVmIiwmZCkKI2RlZmluZSBzZmMoY2gpIHNjYW5mKCIlYyIsJmNoKQojZGVmaW5lIHNmcyhzKSBzY2FuZigiJXMiLHMpCiNkZWZpbmUgcGZkKGQpIHByaW50ZigiJWQiLGQpCiNkZWZpbmUgcGZsZChkKSBwcmludGYoIiVsbGQiLGQpCiNkZWZpbmUgZWwgcHV0Y2hhcignXG4nKQojZGVmaW5lIHNwIHB1dGNoYXIoJyAnKQojZGVmaW5lIEZpbGwoYSx2YWwpIG1lbXNldChhLHZhbCxzaXplb2YgYSkKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBwcGIgcG9wX2JhY2sKI2RlZmluZSBJTkYgMTIzNDU2Nzg5CiNkZWZpbmUgbW9kIDEwMDAwMDAwMDcKI2RlZmluZSBsbCBsb25nIGxvbmcgaW50CiNkZWZpbmUgc2kgc2hvcnQgaW50CiNkZWZpbmUgZ2NkIF9fZ2NkCiNkZWZpbmUgYWxsKGEpIGEuYmVnaW4oKSxhLmVuZCgpCiNkZWZpbmUgVCh4KSBzdHJ0b2soeCwgIiBcblxyXHQiKQp1c2luZyBuYW1lc3BhY2Ugc3RkOwpsbCBGKGxsIG4pewoJcmV0dXJuIG4qKDIqbisxKSoobisxKSooMypuKihuKzEpLTEpLzMwOwp9CmxsIGYobGwgbixsbCBtKXsKICAgICAgICBsbCBjdXIgPSAwLHggPSBuLHJlcyA9IDAsayA9IDE7CiAgICAgICAgd2hpbGUgKDEpewogICAgICAgICAgICAgICB4ID0gbi9rOwogICAgICAgICAgICAgICByZXMgPSAocmVzICsgRih4KSoobi94IC0gY3VyKSklbTsKICAgICAgICAgICAgICAgaWYgKHggPT0gMSkKICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgY3VyID0gbi94OwogICAgICAgICAgICAgICBrID0gbWF4KGsgKyAxICwgbiAvICh4LTEpKTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHJlczsKfQppbnQgbWFpbigpIHsKICAgIGludCB0O3NmZCh0KTsKICAgIHdoaWxlKHQtLSkgewogICAgICAgIGZvcihpbnQgaT0wO2k8dDsrK2kpewogICAgICAgICAgICBsbCBuLG07CiAgICAgICAgICAgIHNmbGQobik7CiAgICAgICAgICAgIHNmbGQobSk7CiAgICAgICAgICAgIHBmbGQoZihuLG0pKTtlbDsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gMDsKfQo=

MTAKMTAwMDAwMDAwMDAgMTAwMDAwCjEwMDAwMDAwMDAwIDEwMDAwMAoxMDAwMDAwMDAwMCAxMDAwMDAKMTAwMDAwMDAwMDAgMTAwMDAwCjEwMDAwMDAwMDAwIDEwMDAwMAoxMDAwMDAwMDAwMCAxMDAwMDAKMTAwMDAwMDAwMDAgMTAwMDAwCjEwMDAwMDAwMDAwIDEwMDAwMAoxMDAwMDAwMDAwMCAxMDAwMDAKMTAwMDAwMDAwMDAgMTAwMDAw

10
10000000000 100000
10000000000 100000
10000000000 100000
10000000000 100000
10000000000 100000
10000000000 100000
10000000000 100000
10000000000 100000
10000000000 100000
10000000000 100000