T=int(input())
for _ in range(T):
    N,M=input().split()
    N=list(N)
    M=int(M)
    p=1
    a=0
    for n in reversed(N):
        a+=p*int(n)
        a%=2*M
        p*=10
        p%=2*M
    b=a
    b+=1
    b%=2*M
    ans=a*b
    ans%=2*M
    ans//=2
    print(ans)