answers = []

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

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