import java.util.*;  
import java.math.BigInteger;  
public class Main{  
    public static void main(String[] args){  
        Scanner in=new Scanner(System.in);  
        int n=in.nextInt();  
        while(n > 0){
            n--;
            BigInteger a = in.nextBigInteger();
            BigInteger b = in.nextBigInteger();
            a = a.subtract( BigInteger.valueOf(1) );
            a = a.subtract( BigInteger.valueOf(1) );
            BigInteger ans = BigInteger.valueOf(1).add(a);
            ans = ans.multiply(a);
            ans = ans.divide(BigInteger.valueOf(2));
            ans = ans.mod(b);
            System.out.println(ans);
        }
    }  
}