import java.math.BigInteger;  
import java.util.*;  
import java.io.*;  
  
public class Main  
{  
    public static void main(String args[])  
    {  
        Scanner in = new Scanner(System.in);  
        int T = in.nextInt();         
        for(int i = 1; i <= T; ++i)  
        {  
            BigInteger q = in.nextBigInteger();  
            BigInteger P = in.nextBigInteger();  
            BigInteger one = BigInteger.ONE;  
            BigInteger two = one.add(one);  
            BigInteger three = two.add(one);  
            
            BigInteger x = q.subtract(three);  
            BigInteger y = x.multiply(q);  
            BigInteger z = y.add(two);   
            BigInteger A = z.divide(two);
            BigInteger ans = A.mod(P);
            System.out.println(ans);  
        }  
    }  
}