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

public class Main {
    public static void main(String args[]){
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out),true);
        int T = cin.nextInt();
        while(cin.hasNext()){
            BigInteger q = cin.nextBigInteger();
            BigInteger P = cin.nextBigInteger();
            BigInteger ans = q.subtract(new BigInteger("2")).multiply(q.subtract(BigInteger.ONE)).divide(new BigInteger("2")).mod(P);
            cout.println(ans);
        }
        
    }

}