Q=int(input()) for _ in range(Q): S,M=input().split() M=int(M) N=len(S) u=[1]*N mod=M 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 result=x*(x+1)//2 result%=mod print(result)