#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
constexpr int inf = 0x3f3f3f3f;

#define Buff ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
//#define int long long

typedef vector<int> vint;

int Ns;
int stm[524288];

void update(int ps, int x, int L = 1, int R = Ns, int p = 1)
{
    if (L == R)
    {
        stm[p] += x;
        return;
    }
    int mid = (L + R) >> 1;
    if (ps <= mid)
        update(ps, x, L, mid, p << 1);
    else
        update(ps, x, mid + 1, R, p << 1 | 1);
    stm[p] = max(stm[p << 1], stm[p << 1 | 1]);
}

int query(int L = 1, int R = Ns, int p = 1)
{
    if (L == R)
        return L;
    int mid = (L + R) >> 1;
    if (stm[p << 1 | 1] == stm[1])
        return query(mid + 1, R, p << 1 | 1);
    else
        return query(L, mid, p << 1);
}

inline void mat(int x, int y)
{
    x--;
    int sp = sqrt(x);
    for (int i = 1; i <= sp; i++)
    {
        if (x % i == 0)
        {
            update(i, y);
            if (i != x / i)
                update(x / i, y);
        }
    }
}

inline int js(int x)
{
    int sp = sqrt(x), ret = 0;
    for (int i = 1; i <= sp; i++)
    {
        if (x % i == 0)
        {
            ret++;
            if (i != x / i)
                ret++;
        }
    }
    return ret;
}

int a[200010];
bool b[200010];

void solve()
{
    int n, q;
    cin >> n >> q;

    if (n == 1)
    {
        int x = 0, y = 0;
        cin >> x;
        cout << "1\n";
        while (q--)
        {
            cin >> x >> y;
            cout << "1\n";
        }
        return;
    }

    Ns = n + 1;
    memset(stm, 0, sizeof(stm));
    for (int i = 1; i <= n; i++)
    {
        b[i] = 0;
        cin >> a[i];
    }
    for (int i = 2; i <= n; i++)
    {
        if (a[i] < a[i - 1])
        {
            b[i] = 1;
            mat(i, 1);
        }
    }
    if (stm[1] == 0)
        cout << n << '\n';
    else
        cout << js(query()) << '\n';
    while (q--)
    {
        int p, x;
        cin >> p >> x;
        if (b[p] && x >= a[p - 1])
        {
            b[p] = 0;
            mat(p, -1);
        }
        else if (!b[p] && x < a[p - 1])
        {
            b[p] = 1;
            mat(p, 1);
        }
        if (p + 1 <= n)
        {
            if (b[p + 1] && a[p + 1] >= x)
            {
                b[p + 1] = 0;
                mat(p + 1, -1);
            }
            else if (!b[p + 1] && a[p + 1] < x)
            {
                b[p + 1] = 1;
                mat(p + 1, 1);
            }
        }
        a[p] = x;
        if (stm[1] == 0)
            cout << n << '\n';
        else
            cout << js(query()) << '\n';
    }
}


signed main()
{
#ifdef YGYYYGJ
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    Buff;
    int _T_ = 1;
    cin >> _T_;
    while (_T_--)
        solve();
    return 0;
}