T = int(input()) for _ in range(T): N,M = input().split() M = int(M) K = len(N) cnt = 0 if int(N[-1])%2==0: for i in range(K-1): cnt = (cnt*10+5*int(N[i]))%M cnt = (cnt+int(N[-1])//2)%M ans = (cnt*(2*cnt+1))%M else: for i in range(K-1): cnt = (cnt*10+5*int(N[i]))%M cnt = (cnt+(int(N[-1])+1)//2)%M ans = (cnt*(2*cnt-1))%M print(ans)