import java.util.*;
import java.math.*;

public class Main {
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            BigInteger q = sc.nextBigInteger();
            BigInteger p = sc.nextBigInteger();
            BigInteger ans = q.multiply(q).subtract(q.multiply(BigInteger.valueOf(3)));
            ans = ans.add(BigInteger.valueOf(2)).divide(BigInteger.valueOf(2));
            ans = ans.remainder(p);
            System.out.println(ans.toString());
        }
    }
}