import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int T;
        BigInteger q,P;
        T = in.nextInt();
        while(T > 0){
            T--;
            q = in.nextBigInteger();
            P = in.nextBigInteger();
            BigInteger s2 = q.multiply(q);
            BigInteger b = q.multiply(BigInteger.valueOf(3));
            BigInteger a = s2.subtract(b).add(BigInteger.valueOf(2)).divide(BigInteger.valueOf(2));
            a = a.mod(P);
            System.out.println(a);
        }
        in.close();
    }
}