Q=int(input()) for _ in range(Q): S,M=input().split() M=int(M) N=len(S) u=[1]*N mod=M if M==1: print(0) continue for i in range(1,N): u[i]=u[i-1]*10 u[i]%=mod x=0 for i in range(N): x+=int(S[-(i+1)])*u[i] x%=mod if M%2==1: result=x*(x+1) result%=mod result*=pow(2,-1,mod) result%=mod print(result) else: result=x*(x+1)//2 result%=mod print(result)