import sys
input = sys.stdin.readline

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