def d(a,b):
  q=0
  for c in a:
    q=q*10+int(c)
    q%=b
  return q

t=int(input())
for _ in range(t):
  n,M=input().split()
  M=int(M)
  a=d(n,2*M)
  print(((a*a+a)%(2*M))//2)