import sys
sys.set_int_max_str_digits(0)
def solve():
    N, M = map(int, input().split())
    ans = N * (N + 1) // 2
    print(ans % M)

def main():
    T = int(input())
    for i in range(T):
        solve()

if __name__ == '__main__':
    main()