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

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

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

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