import java.util.Scanner;
import java.math.*;
public class Main{
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        String s1, s2;

        while(true)
        {    
            if(t == 0)
                break;

            s1 = in.next();
            s2 = in.next();

            BigInteger q = new BigInteger(s1);
            BigInteger P = new BigInteger(s2);

            BigInteger t1 = q.subtract(new BigInteger("2"));
            BigInteger t2 = q.subtract(new BigInteger("1"));
            System.out.println(t1.multiply(t2).divide(new BigInteger("2")).mod(P));
            
            t--;
        }

    }
}