package main

import . "fmt"
import . "os"
import bf "bufio"

// 解説読んで解説のとおりに実装した
// 修行不足

func main() {
	rd:=bf.NewReader(Stdin)
	var t int
	Fscan(rd,&t)
	for ;t>0;t-- {
		var n string
		var m int
		Fscan(rd,&n,&m)
		m*=2
		nd := 0
		for _, c := range n {
			nd = (nd*10 + int(c-'0'))%m
		}
		Println(nd*(nd+1)%m/2)
	}
}