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

def main():
T = int(readline().strip())
results = []
for _ in range(T):
mod = int(readline().strip())
n = int(readline().strip())
ans = 0
for _ in range(n):
a,b = map(int,readline().split())
ans = (ans + pow(a,b, mod)) % mod
results.append(str(ans))

write("\n".join(results)+"\n")

if name == “main”:
main()