for _ in range(int(input())):
	N, M = input().split()
	M = int(M)
	n = 0
	for i in N:
		n = n * 10 + int(i)
		n %= 2 * M
	print(n * (n + 1) // 2 % M)