#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;
    }
    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;
    }
}
long long cnt[N];
void init()
{
    for (int i = 1; i <= 200001; i++)
        for (int j = 1; j * i <= 200001; j++)
            cnt[i * j]++;
}
set<int> st;
int rpos[N];
void solve()
{
    // code
    st.clear();
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        rpos[i] = 0;
        len[i] = 1;
    }
    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 || l == 1)
    {
        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 = n;
        if (l <= pos - 1)
        {
            update(1, l, pos - 1, pos - l);
        }
        if (*nl != *st.rbegin())
        {
            auto rl = nl;
            rl++;
            r = *rl - 1;
        }
        st.insert(pos);
        if (pos + 1 <= r)
        {
            st.insert(pos + 1);
            update(1, pos + 1, r, r - pos);
        }
        nl = st.find(pos);
        if (*nl == *st.begin() && *nl == *st.rbegin())
        {
            cout << 1 << '\n';
            continue;
        }
        if (*nl == *st.begin())
        {
            auto rr = nl;
            rr++;
            int r1 = *rr, r2 = n;
            if (*rr != *st.rbegin())
            {
                rr++;
                r2 = (*rr) - 1;
            }
            if (a[pos] <= a[r1])
            {
                st.erase(r1);
                update(1, pos, r2, r2 - pos + 1);
            }
        }
        else if (*nl == *st.rbegin())
        {
            auto ll = nl;
            ll--;
            int l1 = *ll, l2 = pos - 1;
            if (a[pos] >= a[l2])
            {
                st.erase(pos);
                update(1, l1, pos, pos - l1 + 1);
            }
        }
        else
        {
            auto ll = nl;
            ll--;
            int l1 = *ll, l2 = pos - 1;
            auto rr = nl;
            rr++;
            int r1 = pos + 1, r2 = n;
            if (*rr != *st.rbegin())
            {
                rr++;
                r2 = (*rr) - 1;
            }
            if (a[pos] >= a[l2] && a[pos] <= a[r1])
            {
                st.erase(pos);
                st.erase(r1);
                update(1, l1, r2, r2 - l1 + 1);
            }
            else if (a[pos] >= a[l2])
            {
                st.erase(pos);
                update(1, l1, pos, pos - l1 + 1);
            }
            else if (a[pos] <= a[r1])
            {
                st.erase(r1);
                update(1, pos, r2, r2 - pos + 1);
            }
        }
        int x = *st.rbegin();
        int g = ask(1, 1, x - 1);
        if (g == 0 || x == 1)
        {
            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;
}