for _ in range(int(input())):
	s, mod = input().split()
	mod = int(mod)
	res = 0
	for i in s:
		res = (res * 10 + (ord(i) - ord('0'))) % (mod * 2)
	print((res * (res + 1) // 2) % mod)