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

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