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