#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 1000010;
int s[N], a[N], d[N * 4];
int getd(int x)
{
    int res = 0;
    for (int i = 1; i <= x / i; i++)
    {
        if (x % i == 0)
        {
            res++;
            if (i != x / i)
                res++;
        }
    }
    // sort(res.begin(), res.end());
    return res;
}
void pushdown(int p)
{
    if (!d[2 * p] && !d[2 * p + 1])
    {
        d[p] = 0;
    }
    else if (d[2 * p] && !d[2 * p + 1])
    {
        d[p] = d[2 * p];
    }
    else if (!d[2 * p] && d[2 * p + 1])
    {
        d[p] = d[p * 2 + 1];
    }
    else
    {
        d[p] = __gcd(d[p * 2], d[p * 2 + 1]);
    }
}
void build(int s, int t, int p)
{
    // cout << s << " " << t << " " << p << endl;
    if (s == t)
    {
        // cout << p << " " << a[s] << endl;
        d[p] = a[s];
        return;
    }
    int mid = (s + t) >> 1;
    build(s, mid, p * 2), build(mid + 1, t, p * 2 + 1);
    pushdown(p);
}
void chenge(int s, int t, int e, int c, int p)
{
    if (s == t)
    {
        d[p] = c;
        return;
    }
    int mid = (s + t) >> 1;
    if (mid >= e)
        chenge(s, mid, e, c, p * 2);
    else
        chenge(mid + 1, t, e, c, p * 2 + 1);
    pushdown(p);
}
void solve()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        a[i] = 0;
    }
    s[n + 1] = 5e9;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] > s[i + 1])
            a[i] = i;
    }
    // cout << endl;
    build(1, n, 1);
    // cout << d[4] << " **" << d[1] << endl;
    int t = d[1];
    if (t == 0)
        t = n;
    cout << getd(t) << endl;
    // cout << t << endl;
    while (q--)
    {
        int p, v;
        cin >> p >> v;
        if (s[p] > s[p + 1] && v <= s[p + 1])
        {
            chenge(1, n, p, 0, 1);
        }
        if (s[p] <= s[p + 1] && v > s[p + 1])
        {
            chenge(1, n, p, p, 1);
        }
        if (s[p - 1] > s[p] && s[p - 1] <= v && p >= 2)
        {
            chenge(1, n, p - 1, 0, 1);
        }
        if (s[p - 1] <= s[p] && s[p - 1] > v && p >= 2)
        {
            chenge(1, n, p - 1, p - 1, 1);
        }
        s[p] = v;
        int t = d[1];
        if (t == 0)
            t = n;
        // cout << " " << t << endl;
        cout << getd(t) << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}