T = int(input())

for _ in range(T):
    N, M = map(str, input().split())
    M = int(M)*2
    K = 0
    for n in N:
        K = (K*10 + int(n))%M
    ans = (K*(K+1))%M
    print(ans//2)