T=int(input())
for _ in range(0,T):
    n,m=input().split()
    m=int(m)
    m*=2
    x=0
    for c in n:
        d=int(c)
        x=x*10+d
        x%=m
    y=(x+1)%m
    ans=x*y%m//2
    print(ans)