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