def solve(n,m):
    m=int(m)
    tmp=0
    for c in n:
        tmp=10*tmp+int(c)
        tmp%=(2*m)
    return (tmp*(tmp+1)//2)%m

print(*[solve(*input().split()) for i in range(int(input()))],sep='\n')