from sys import set_int_max_str_digits as s
s(0)
R=range
J=lambda:map(int,input().split())
for t in R(sum(J())):
	N,M=J();n=N-1
	for j in R(M):K,*_=J();print((1if N<1else(pow(N,K+1,n*998)-1)//n if N>1else K+1)%998)