def solve():
    N, M = input().split()
    M = int(M)

    N_mod = 0
    for i in range(len(N)):
        N_mod = (10 * N_mod + int(N[i])) % (2 * M)

    return (N_mod * (N_mod + 1) % (2 * M)) // 2

#==================================================
import sys
input=sys.stdin.readline
write=sys.stdout.write

T=int(input())
write("\n".join(map(str, [solve() for _ in range(T)])))