T=int(input())
for i in range(T):
  #D,A=map(int,input().split())
  N,M=input().split()
  #N=int(input())
  #X=list(map(int, input().split()))
  M=int(M)
  #ansb=((1+NN)*NN//2)%M
  M*=2 
  now=0;p=1  
  for s in N[::-1]:
    s=int(s)
    now+=p*s 
    now%=M 
    p*=10
    p%=M 
  d=(now*(now+1))
  ans=d%M 
  print(ans//2)