import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t;
        t = in.nextInt();
        BigInteger q, p;
        BigInteger t1;
        BigInteger t2;
        while (t > 0) {
            t--;
            q = in.nextBigInteger();
            p = in.nextBigInteger();
            BigInteger ans;

            t1 = q.subtract(BigInteger.valueOf(1));
            t2 = q.subtract(BigInteger.valueOf(2));
            ans = t1.multiply(t2);
            ans = ans.divide(BigInteger.valueOf(2));
            System.out.println(ans.mod(p));
        }
        in.close();
    }
    
}