answers = []

for _ in range(int(input())):
    nstr, mstr = input().split()
    m = int(mstr)
    md = 0
    for c in nstr:
        md = (md * 10 + int(c)) % (m * 2)
    answers.append(md * (md + 1) // 2 % m)

print(*answers, sep='\n')