package main

import . "fmt"
import . "os"
import bf "bufio"
import . "math/big"

func main() {
	rd:=bf.NewReader(Stdin)
	var t int
	Fscan(rd,&t)
	n,m := new(Int),new(Int)
	for ;t>0;t-- {
		Fscan(rd,n,m)
		n.Mod(n,m)
		nn, mm := n.Int64(), m.Int64()
		Println(nn*(nn+1)/2%mm)
	}
}