import java.util.Scanner;


public class Main {
    public static int expmod(int n, int e, int m) {
	int r = n % m;
	int rr = 1;
	while(e > 0) {
	    if((e & 1) == 1)
	    	rr = rr * r % m;
	    r = r * r % m;
	    
	    e >>= 1;
	}
	
	
	return rr;
    }
    
    public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	int z = in.nextInt();
	while(z-->0) {
	    int r = 0;
	    int m = in.nextInt();
	    int g = in.nextInt();
	    while(g-->0) {
		int n = in.nextInt();
		int e = in.nextInt();
		r += expmod(n, e, m);
	    }
	    System.out.println(r % m);
	}
	
    }
}