#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;

inline char gtc()
{
    static char BB[2000000], *S = BB, *T = BB;
    return S == T && (T = (S = BB) + fread(BB, 1, 2000000, stdin), S == T) ? EOF : *S++;
}

typedef long long ll;
inline int read()
{
    int x = 0, f = 1;
    char ch = gtc();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = gtc();
    }
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = gtc();
    return x * f;
}

inline void write(int x)
{
    if (x == 0)
    {
        putchar('0');
        return;
    }
    int len = 0;
    static char c[25];
    if (x < 0) x = -x, putchar('-');
    while (x) c[len++] = x % 10 + '0', x /= 10;
    while (len--) putchar(c[len]);
    putchar('\n');
}

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 = read(), q = read();

    if (n == 1)
    {
        int x = read();
        write(1);
        while (q--)
        {
            x = read();
            x = read();
            write(1);
        }
        return;
    }

    Ns = n + 1;
    memset(stm, 0, sizeof(stm));
    for (int i = 1; i <= n; i++)
    {
        b[i] = 0;
        a[i] = read();
    }
    for (int i = 2; i <= n; i++)
    {
        if (a[i] < a[i - 1])
        {
            b[i] = 1;
            mat(i, 1);
        }
    }
    if (stm[1] == 0)
        write(n);
    else
        write(js(query()));
    while (q--)
    {
        int p = read(), x = read();
        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)
            write(n);
        else
            write(js(query()));
    }
}


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