import sys
input = sys.stdin.readline
t=int(input())
for _ in range(t):
  n,m=map(str,input().split())
  m=int(m)
  le=len(n)
  po=(10**20)%m
  now=1
  ans=0
  for i in range(le//20):
    s=int(n[le-20*(i+1):le-20*i])
    ans+=(s*now)%m
    ans%=m
    now*=po
    now%=m
  s=int(n[:le%20])
  ans+=(s*now)%m
  ans%=m
  ans=(ans*(ans+1))//2
  print(ans%m)