T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    if N % 2 == 0:
        print(((N // 2) % M) * ((N % M + 1)) % M)
    else:
        print((((N + 1) // 2) % M) * (N % M) % M)