import sys
sys.set_int_max_str_digits(5000000)
T=int(input())

for _ in range(T):
	a,b=map(int,input().split())
	if(a%2==0):
		res=(a//2)%b*(a+1)%b
		res%=b
		print(res)
	else:
		res=a%b*((a+1)//2)%b
		res%=b
		print(res)