import java.math.BigDecimal;
import java.util.Scanner;
import java.math.BigInteger;
public class Main
{
    public static void main(String[] args)
    {
        Scanner s = new Scanner(System.in);
        int t=s.nextInt();
        while(true)
        {
            if(t==0)
                break;
            BigInteger q=s.nextBigInteger();
            BigInteger p=s.nextBigInteger();
            q=q.add(BigInteger.valueOf(-1));
            BigInteger sum;
            sum=q.multiply(q.add(BigInteger.valueOf(-1)));
            sum=sum.divide(BigInteger.valueOf(2));
            sum=sum.mod(p);
            System.out.println(sum);
            t--;
        }
    }
}