Main(require("fs").readFileSync("/dev/stdin", "utf8").split("\n"));

function Main(lines) {
    const T = parseInt(lines[0]);
    for(let i=0; i<T; ++i) {
        // NM = lines[i+1].split(" ").map((x)=>BigInt(x));
        const NM = lines[i+1].split(" ").map(BigInt);
        const M = NM[1];
        const N = NM[0];
        const ans = N*(N+1n)/2n%M;
        console.log(ans.toString());
    }
}