import java.util.*;
import java.math.*;
public class Main
   {
     public static void main(String args[])  {
    Scanner cin=new Scanner(System.in);
    int t=cin.nextInt();
    while(t!=0)
    {t--;
    BigInteger q,P,i,j,ans;
    q=cin.nextBigInteger();
    P=cin.nextBigInteger();
    j=new BigInteger("1");
    if(q.equals("1")||q.equals("2")){System.out.println("0");continue;}
    q=q.subtract(BigInteger.valueOf(2));
    ans = q.multiply( q.add(BigInteger.valueOf(1)) );
      ans = ans.divide(BigInteger.valueOf(2));
      System.out.println(ans.mod(P));
    }
     }
   }