// 1加快输入输出：要使用此种优化读入速度的方式则需要仅仅使用rd()输入，不可交叉使用cin
#include <stdio.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
int rd()
{
    int k = 0, f = 1;
    char s = getchar();
    while (s < '0' || s > '9')
    {
        if (s == '-')
            f = 0;
        s = getchar();
    }
    while (s >= '0' && s <= '9')
    {
        k = (k << 1) + (k << 3) + (s ^ '0');
        s = getchar();
    }
    return f ? k : -k;
}
void wr(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        wr(x / 10);
    putchar((x % 10) ^ '0');
}

#include <iostream>

using namespace std;

using ll = long long;

// 2 将模运算转化为乘法和加减

// 快速幂取模
ll fast_power_mod(ll base, ll power, ll mod)
{
    ll result = 1;
    while (power > 0)
    {
        if (power & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        power >>= 1;
    }
    return result;
}

void solve()
{
    int m;
    m = rd();
    int h;
    h = rd();
    ll res = 0;
    for(int i = 0; i < h; i ++ )
    {
        ll a, b;
        a = rd();
        b = rd();
        res = (res + fast_power_mod(a, b, m)) % m;
    }
    wr(res);
    puts("");
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = rd();
    while (t--)
    {
        solve();
    }

    return 0;
}