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