POJ 1995

#include <iostream>
#include <cstdio>
using namespace std;

int quick(int a,int b,int m){
	int ans=1;
	a%=m;
	while(b){
		if(b&1){
			ans=(ans*a)%m;
			b--;
		}
		a=(a*a)%m;
		b/=2;
	}
	return ans;
}

int main(){
	int t;
	scanf("%d",&t);
	int m,n; int ans,a,b;
	while(t--){
		ans=0;
		scanf("%d",&m);
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			scanf("%d%d",&a,&b);
			ans=(ans+quick(a,b,m))%m;
		}
		printf("%d\n",ans%m);
	}
	return 0;
}