#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int, int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int T;
#define ls u << 1
#define rs u << 1 | 1
struct tree
{
    int l, r, w, lazy;
} tr[N * 4];
int n, m, a[N], len[N];
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
void pushup(int u)
{
    tr[u].w = gcd(tr[ls].w, tr[rs].w);
}
void pushdown(int u)
{
    if (tr[u].lazy)
    {
        tr[ls].w = tr[rs].w = tr[u].lazy;
        tr[ls].lazy = tr[rs].lazy = tr[u].lazy;
        tr[u].lazy = 0;
    }
}
void build(int u, int l, int r)
{
    if (l == r)
    {
        tr[u] = {l, l, len[l], 0};
        return;
    }
    tr[u] = {l, r, 0, 0};
    long long mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(u);
}
void update(int u, int l, int r, int v)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].w = v;
        tr[u].lazy = v;
        return;
    }
    else
    {
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid)
            update(ls, l, r, v);
        if (r > mid)
            update(rs, l, r, v);
        pushup(u);
    }
}
int ask(int u, int l, int r)
{
    if (l > r)
    {
        return 0;
    }
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].w;
    }
    else
    {
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        int ans = 0;
        if (l <= mid)
            ans = gcd(ans, ask(ls, l, r));
        if (r > mid)
            ans = gcd(ans, ask(rs, l, r));
        return ans;
    }
}
vector<int> p;
bool np[N];
int cnt[N];
void init()
{
    for (int i = 1; i <= 200000; ++i)
        for (int j = 1; j * i <= 200000; ++j)
            cnt[i * j]++;
}

set<int> st;
int rpos[N];
void solve()
{
    // code
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        int j = i;
        while (j + 1 <= n && a[j] <= a[j + 1])
        {
            j++;
        }
        for (int k = i; k <= j; k++)
        {
            len[k] = (j - i + 1);
        }
        st.insert(i);
        rpos[i] = j;
        i = j;
    }
    build(1, 1, n);
    int l = *st.rbegin();
    int g = ask(1, 1, l - 1);
    if (g == 0)
    {
        cout << n << '\n';
    }
    else
    {
        cout << cnt[g] << '\n';
    }
    while (m--)
    {
        int pos, v;
        cin >> pos >> v;
        a[pos] = v;
        auto nl = st.lower_bound(pos);
        int l = *nl, r = rpos[l];
        if (l <= pos - 1)
        {
            rpos[l] = pos - 1;
            update(1, l, pos - 1, pos - l);
        }
        rpos[pos] = pos;
        update(1, pos, pos, 1);
        if (pos + 1 <= r)
        {
            st.insert(pos + 1);
            rpos[pos + 1] = r;
            update(1, pos + 1, r, r - pos);
        }
        nl = st.lower_bound(pos);
        auto en = st.end();
        en--;
        if (nl == st.begin() && nl == en)
        {
            cout << 1 << '\n';
            continue;
        }
        if (nl == st.begin())
        {
            auto rq = nl;
            rq++;
            int rl = *rq, rr = rpos[rl];
            if (a[pos] <= a[rl])
            {
                st.erase(rl);
                rpos[pos] = rr;
                update(1, pos, rr, rr - pos + 1);
            }
        }
        else if (nl == en)
        {
            auto lq = nl;
            lq--;
            int ll = *lq, lr = rpos[ll];
            if (a[pos] >= a[lr])
            {
                st.erase(pos);
                rpos[ll] = pos;
                update(1, ll, pos, pos - ll + 1);
            }
        }
        else
        {
            auto lq = nl;
            lq--;
            auto rq = nl;
            rq++;
            int l1 = *lq, l2 = rpos[l1];
            int r1 = *rq, r2 = rpos[r1];
            if (a[pos] >= a[l2] && a[pos] <= a[r1])
            {
                st.erase(pos);
                st.erase(r1);
                rpos[l1] = r2;
                update(1, l1, r2, r2 - l1 + 1);
            }
            else if (a[pos] >= a[l2])
            {
                st.erase(pos);
                rpos[l1] = pos;
                update(1, l1, pos, pos - l1 + 1);
            }
            else if (a[pos] <= a[r1])
            {
                st.erase(r1);
                rpos[pos] = r2;
                update(1, pos, r2, r2 - pos + 1);
            }
        }
        int x = *st.rbegin();
        int g = ask(1, 1, x - 1);
        if (g == 0)
        {
            cout << n << '\n';
        }
        else
        {
            cout << cnt[g] << '\n';
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}