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,h := new(Int),new(Int),new(Int)
	one := NewInt(1)
	for ;t>0;t-- {
		Fscan(rd,n,m)
		if h.Add(n,one).Bit(0) == 0 {
			h.Rsh(h,1)
		} else {
			n.Rsh(n,1)
		}
		n.Mod(n,m)
		h.Mod(h,m)
		Println(n.Int64()*h.Int64()%m.Int64())
	}
}