import sys
sys.set_int_max_str_digits(0)
for _ in range(int(input())):
	N,M=map(int,input().split())
	a=N%(2*M)
	b=(N+1)%(2*M)
	print(a*b//2%M)