// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#define INF 0x3fffffff
#define overload3(a, b, c, d, ...) d
#define overload4(a, b, c, d, e, ...) e
#define all1(x) (x).begin(), (x).end()
#define all2(x, i) (x).begin() + (i), (x).end()
#define all3(x, i, j) (x).begin() + (i), (x).begin() + (j)
#define all(...) overload3(__VA_ARGS__, all3, all2, all1)(__VA_ARGS__)
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define eb emplace_back
#define mkp make_pair
#define lowbit(x) (x & -x)
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define REP1(a) for (ll _ = 1; _ <= a; ++_)
#define REP2(i, a) for (ll i = 1; i <= ll(a); ++i)
#define REP3(i, a, b) for (ll i = (a); i <= ll(b); ++i)
#define REP4(i, a, b, c) for (ll i = (a); i <= ll(b); i += (c))
#define PER(i, a, b) for (ll i = (a); i >= ll(b); --i)
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define REP(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define MT       \
    int tt;      \
    cin >> tt;   \
    while (tt--) \
    {            \
        solve(); \
    }
#define suffZero(x) (__builtin_ctz(x))
#define suffZeroll(x) (__builtin_ctzll(x))
#define preZero(x) (__builtin_clz(x))
#define preZeroll(x) (__builtin_clzll(x))
#define countOne(x) (__builtin_popcount(x))
#define countOnell(x) (__builtin_popcountll(x))
#define lastOne(x) (__builtin_ffs(x))
#define firstOne(x) (32 - preZero(x))
#define firstOnell(x) (64 - preZeroll(x))
#ifdef LOCAL
#include "dbg.h"
#else
#define dbg(...) (__VA_ARGS__)
#endif
using namespace std;
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vector<pii>> vvpii;
typedef vector<vector<int>> vvi;
mt19937_64 rng{chrono::steady_clock::now().time_since_epoch().count()};
#define endl '\n'
vvi dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}};

int fac[int(2e5 + 10)];

class segtree // 只需要写 apply、pushdown、merge
{
public:
    int ls(int x) { return x << 1; }
    int rs(int x) { return x << 1 | 1; }
    struct node
    {
        // don't forget to set default value (used for leaves)
        // not necessarily neutral element!
        ll gcd = 0, add = 0;
        void apply(int l, int r, ll v)
        {
            gcd += v, add += v;
        }
    };
    int n;
    vector<node> tree;

    node merge(const node &a, const node &b) const
    {
        node res;
        res.gcd = gcd(a.gcd, b.gcd);
        return res;
    }

    inline void pushdown(int x, int l, int r)
    {
        int m = (l + r) >> 1;
        // pushdown from x into ls(x) and rs(x)
        if (tree[x].add != 0)
        {
            tree[ls(x)].apply(l, m, tree[x].add);
            tree[rs(x)].apply(m + 1, r, tree[x].add);
            tree[x].add = 0;
        }
    }

    inline void pushup(int x)
    {
        tree[x] = merge(tree[ls(x)], tree[rs(x)]);
    }

    void build(int x, int l, int r)
    {
        if (l == r)
        {
            return;
        }
        int m = (l + r) >> 1;
        build(ls(x), l, m), build(rs(x), m + 1, r);
        pushup(x);
    }

    template <typename M>
    void build(int x, int l, int r, const vector<M> &v)
    {
        if (l == r)
        {
            tree[x].apply(l, r, v[l]);
            return;
        }
        int m = (l + r) >> 1;
        build(ls(x), l, m, v), build(rs(x), m + 1, r, v);
        pushup(x);
    }

    node query(int x, int l, int r, int L, int R)
    {
        if (L <= l && r <= R)
        {
            return tree[x];
        }
        int m = (l + r) >> 1;
        pushdown(x, l, r);
        node res{};
        if (R <= m)
            res = query(ls(x), l, m, L, R);
        else if (L > m)
            res = query(rs(x), m + 1, r, L, R);
        else
            res = merge(query(ls(x), l, m, L, R), query(rs(x), m + 1, r, L, R));
        pushup(x);
        return res;
    }

    template <typename... M>
    void modify(int x, int l, int r, int L, int R, const M &...v)
    {
        if (L <= l && r <= R)
        {
            tree[x].apply(l, r, v...);
            return;
        }
        int m = (l + r) >> 1;
        pushdown(x, l, r);
        if (L <= m)
            modify(ls(x), l, m, L, R, v...);
        if (R > m)
            modify(rs(x), m + 1, r, L, R, v...);
        pushup(x);
    }

    void modify(int x, int l, int r, int p, const node v)
    {
        if (l == r)
        {
            tree[x] = v;
            return;
        }
        int m = (l + r) >> 1;
        pushdown(x, l, r);
        if (p <= m)
            modify(ls(x), l, m, p, v);
        if (p > m)
            modify(rs(x), m + 1, r, p, v);
        pushup(x);
    }

    int find_first_knowingly(int x, int l, int r, const function<bool(const node &)> &f)
    {
        if (l == r)
        {
            // return f(tree[x]) ? l : 0;
            return l;
        }
        pushdown(x, l, r);
        int m = (l + r) >> 1;
        int res;
        if (f(tree[ls(x)]))
            res = find_first_knowingly(ls(x), l, m, f);
        else
            res = find_first_knowingly(rs(x), m + 1, r, f);
        pushup(x);
        return res;
    }

    int find_first(int x, int l, int r, int L, int R, const function<bool(const node &)> &f)
    {
        if (L <= l && r <= R)
        {
            if (!f(tree[x]))
                return 0;
            return find_first_knowingly(x, l, r, f);
        }
        pushdown(x, l, r);
        int m = (l + r) >> 1;
        int res = 0;
        if (L <= m)
            res = find_first(ls(x), l, m, L, R, f);
        if (R > m && res == 0)
            res = find_first(rs(x), m + 1, r, L, R, f);
        pushup(x);
        return res;
    }

    int find_last_knowingly(int x, int l, int r, const function<bool(const node &)> &f)
    {
        if (l == r)
        {
            // return f(tree[x]) ? l : 0;
            return l;
        }
        pushdown(x, l, r);
        int m = (l + r) >> 1;
        int res;
        if (f(tree[rs(x)]))
            res = find_last_knowingly(rs(x), m + 1, r, f);
        else
            res = find_last_knowingly(ls(x), l, m, f);
        pushup(x);
        return res;
    }

    int find_last(int x, int l, int r, int L, int R, const function<bool(const node &)> &f)
    {
        if (L <= l && r <= R)
        {
            if (!f(tree[x]))
                return 0;
            return find_last_knowingly(x, l, r, f);
        }
        pushdown(x, l, r);
        int m = (l + r) >> 1;
        int res = 0;
        if (R > m)
            res = find_last(rs(x), m + 1, r, L, R, f);
        if (L <= m && res == 0)
            res = find_last(ls(x), l, m, L, R, f);
        pushup(x);
        return res;
    }

    segtree(int _n) : n(_n)
    {
        assert(n > 0);
        tree.resize(n << 2);
        build(1, 1, n);
    }

    template <typename M>
    segtree(const vector<M> &v)
    {
        n = v.size() - 1;
        assert(n > 0);
        tree.resize(n << 2);
        build(1, 1, n, v);
    }

    node query(int L, int R)
    {
        assert(1 <= L && L <= R && R <= n);
        return query(1, 1, n, L, R);
    }

    node query(int p)
    {
        assert(1 <= p && p <= n);
        return query(1, 1, n, p, p);
    }

    template <typename... M>
    void modify(int L, int R, const M &...v)
    {
        assert(1 <= L && L <= R && R <= n);
        modify(1, 1, n, L, R, v...);
    }

    void modify(int x, const node v)
    {
        assert(1 <= x && x <= n);
        modify(1, 1, n, x, v);
    }

    // find_first 和 find_last 只会在false的元素搜索最多一次
    // 只能用来求解大区间满足则小区间满足的性质，如最值

    int find_first(int L, int R, const function<bool(const node &)> &f)
    {
        assert(1 <= L && L <= R && R <= n);
        return find_first(1, 1, n, L, R, f);
    }

    int find_last(int L, int R, const function<bool(const node &)> &f)
    {
        assert(1 <= L && L <= R && R <= n);
        return find_last(1, 1, n, L, R, f);
    }
};

ostream &operator<<(ostream &out, const segtree::node &a) // 重载ostream可以通过debug输出tree数组的内容
{
    out << " [gcd=" << a.gcd << " add=" << a.add << "] ";
    return out;
}

ll mul(ll a, ll b, ll m)
{
    return static_cast<__int128>(a) * b % m;
}
ll power(ll a, ll b, ll m)
{
    ll res = 1 % m;
    for (; b; b >>= 1, a = mul(a, a, m))
        if (b & 1)
            res = mul(res, a, m);
    return res;
}
bool isprime(ll n)
{
    if (n < 2)
        return false;
    static constexpr int A[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    int s = __builtin_ctzll(n - 1);
    ll d = (n - 1) >> s;
    for (auto a : A)
    {
        if (a == n)
            return true;
        ll x = power(a, d, n);
        if (x == 1 || x == n - 1)
            continue;
        bool ok = false;
        for (int i = 0; i < s - 1; ++i)
        {
            x = mul(x, x, n);
            if (x == n - 1)
            {
                ok = true;
                break;
            }
        }
        if (!ok)
            return false;
    }
    return true;
}
int factorize(ll n)
{
    assert(n >= 1);
    vector<ll> p;
    function<void(ll)> f = [&](ll n)
    {
        if (n <= 10000)
        {
            for (int i = 2; i * i <= n; ++i)
                for (; n % i == 0; n /= i)
                    p.push_back(i);
            if (n > 1)
                p.push_back(n);
            return;
        }
        if (isprime(n))
        {
            p.push_back(n);
            return;
        }
        auto g = [&](ll x)
        {
            return (mul(x, x, n) + 1) % n;
        };
        ll x0 = 2;
        while (true)
        {
            ll x = x0;
            ll y = x0;
            ll d = 1;
            ll power = 1, lam = 0;
            ll v = 1;
            while (d == 1)
            {
                y = g(y);
                ++lam;
                v = mul(v, abs(x - y), n);
                if (lam % 127 == 0)
                {
                    d = gcd(v, n);
                    v = 1;
                }
                if (power == lam)
                {
                    x = y;
                    power *= 2;
                    lam = 0;
                    d = gcd(v, n);
                    v = 1;
                }
            }
            if (d != n)
            {
                f(d);
                f(n / d);
                return;
            }
            ++x0;
        }
    };
    f(n);
    sort(p.begin(), p.end());
    if (p.empty())
        return 0;
    ll cur = p[0];
    int pos = 0;
    int res = 1;
    while (pos < sz(p))
    {
        int q = 0;
        while (p[pos] == cur)
        {
            q++;
            pos++;
        }
        res *= q + 1;
        cur = p[pos];
        q = 0;
    }
    return res;
}

void solve()
{
    int n, q;
    cin >> n >> q;
    vi a(n + 1);
    REP(i, 1, n)
    {
        cin >> a[i];
    }
    vi g(n + 1);
    REP(i, 1, n - 1)
    {
        if (a[i] > a[i + 1])
            g[i] = i;
    }
    segtree s(g);
    int res = s.tree[1].gcd;
    cout << (res != 0 ? fac[res] : n) << endl;
    REP(i, 1, q)
    {
        int p, x;
        cin >> p >> x;
        a[p] = x;
        if (p < n)
        {
            if (a[p] > a[p + 1])
                s.modify(p, {p, 0});
            else
            {
                s.modify(p, {0, 0});
            }
        }
        if (p > 1)
        {
            if (a[p - 1] > a[p])
                s.modify(p - 1, {p - 1, 0});
            else
            {
                s.modify(p - 1, {0, 0});
            }
        }
        int res = s.tree[1].gcd;
        cout << (res != 0 ? fac[res] : n) << endl;
    }
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    clock_t st = clock();
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    //-------------------------------------
    fac[1] = 1;
    int mx = 0;
    int ind = 0;
    REP(i, 2, 2e5)
    {
        fac[i] = factorize(i);
    }
    MT;
//-------------------------------------
#ifdef LOCAL
    cerr << "Time:" << clock() - st << "ms\n";
#endif
    return 0;
}