def solve():
    N, M = map(str, input().split(' '))
    M = int(M)
    r = 0
    for i in range(len(N)):
        r = (10 * r + int(N[i])) % (2 * M)
    print((r * (r + 1) // 2) % M)



T = int(input())
for _ in range(T):
    solve()