import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main
{
    public static void main(String args[])
    {
        Scanner cin = new Scanner(System.in);    
        int T = cin.nextInt();
        while(T-- != 0)
        {
            BigInteger n = cin.nextBigInteger();
            BigInteger p = cin.nextBigInteger();
            BigInteger ans = BigInteger.ZERO;
            n = n.subtract(BigInteger.valueOf(2));
            ans = n.multiply( n.add(BigInteger.valueOf(1)) );
            ans = ans.divide(BigInteger.valueOf(2));
            System.out.println(ans.mod(p));
        }
    }
}