每个股票的价值等于其编号的阶乘(例如编号为5的股票的价值就是120)。
由此可知，一个大于P的质数的股票价值W = 1*2*3*.......*P*P+1*....;那么他的价值对P求余W%P=0；所以只要考虑P前面的数字就OK了，也就是从1E8缩小到了1E5，用欧拉筛就可以了
然后遍历，当N比P大时比P的一部分可以直接省去，因为阶乘对P求余等于0，当N比P小那就是直接求2~N，也就是遍历2 ~ min（N，P）;
用s记录阶乘，当是质数的时候就把s加到sum这个结果里面。 
//大于P的质数的阶乘对P求余等于0
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int prim[N],a[N];  //a[ i ]用来存i是不是质数，等于0为质数
int t,n,p;
void primes()   //欧拉筛求质数，最快的方法
{
    int cnt=0;
    for(int i=2;i<=N;i++)
    {
        if(!a[i])prim[cnt++]=i;
        for(int j=0;prim[j]<=N/i;j++)
        {
            a[prim[j]*i]=1;
            if(i%prim[j]==0)break;
        }
    }
}
int main()
{
    primes();
    scanf("%d",&t);
    while(t--)
    {
        ll s=1,sum=0;
        scanf("%d%d",&n,&p);
        for(int i=2;i<=min(n,p);i++)   //从2枚举到min(n,p)
        {
            s=(s*i)%p;  //s是阶乘,要开long long
            if(!a[i])
              sum=(sum+s)%p;  //sum是结果
        }
        
        cout<<sum<<endl;
    }
    
    return 0;
}