#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define LL __int64using namespace std;LL M;LL quick(LL a,LL b){	a%=M;	LL ans=1;	while(b){		if(b&1)		ans=(ans*a)%M;		b>>=1;		a=(a*a)%M;	}	return ans;}int main(){	int T,n;	LL a,b;	scanf("%d",&T);	while(T--){		LL ans=0;		scanf("%I64d",&M);		scanf("%d",&n);		for(int i=1;i<=n;i++){			scanf("%I64d%I64d",&a,&b);			ans=(ans+quick(a,b))%M;		}		printf("%I64d\n",ans);	}	return 0;}