I=input
for t in range(int(I())):
	S,M=I().split()
	N,M=0,int(M)
	for s in S:N=(N*10+int(s))%(M*2)
	print(N*(N+1)//2%M)