#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 2e5 + 10, mod = 998244353, INF = 0x3f3f3f3f;
random_device rd;
mt19937_64 rng(rd());

LL n, m;
LL a[N];

template<class Info,class Tag>
struct LST{
    int n;
    vector<Info> tr;
    vector<Tag> tag;
    LST(int n) : n(n),tr(n << 2),tag(n << 2) {}
    LST(vector<Info> a) : LST(a.size() - 1){
        auto build = [&](auto self,int rt,int l,int r)->void{
            if(l == r){
                tr[rt] = a[l];
                return;
            }
            int mid = (l + r) >> 1;
            self(self,rt << 1,l,mid);
            self(self,rt << 1 | 1,mid + 1,r);
            push_up(rt);
        };
        build(build,1,1,n);
    }
    void push_up(int rt){
        tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
    }
    void apply(int rt,int l,int r,const Tag& v){
        tr[rt].apply(l,r,v);
        tag[rt].apply(v);
    }
    void push_down(int rt,int l,int r){
        int mid = (l + r) >> 1;
        apply(rt << 1,l,mid,tag[rt]);
        apply(rt << 1 | 1,mid + 1,r,tag[rt]);
        tag[rt] = Tag();
    }
    void modify(int rt,int l,int r,int x,int y,const Tag& v){
        if(x <= l && r <= y){
            apply(rt,l,r,v);
            return;
        }
        // push_down(rt,l,r);
        int mid = (l + r) >> 1;
        if(x <= mid)modify(rt << 1,l,mid,x,y,v);
        if(y > mid)modify(rt << 1 | 1,mid + 1,r,x,y,v);
        push_up(rt);
    }
    void modify(int x,int y,const Tag& v){modify(1,1,n,x,y,v);}
    Info query(int rt,int l,int r,int x,int y){
        if(x <= l && r <= y){
            return tr[rt];
        }
        // push_down(rt,l,r);
        int mid = (l + r) >> 1;
        if(x <= mid && y > mid)return query(rt << 1,l,mid,x,y) + query(rt << 1 | 1,mid + 1,r,x,y);
        else if(x <= mid)return query(rt << 1,l,mid,x,y);
        else return query(rt << 1 | 1,mid + 1,r,x,y);
    }
    Info query(int x,int y){return query(1,1,n,x,y);}
};

struct Tag{
    LL d;
    Tag(LL v = 0) {d = v;}
    void apply(Tag t){
        d = t.d;
    }
};

struct Info{
    LL g;
    Info(LL v = 0){
        g = v;
    }
    void apply(int l,int r,Tag v){
        g = v.d;
    }
};

Info operator+(Info a,Info b){
    Info c;
    c.g = __gcd(a.g, b.g);
    return c;
}

LL prime[N], cnt, st[N];
LL p1[N];// p[i]为i的欧拉函数,欧拉函数为1~n与n互质的个数
/*
N = a1(b1) * a2(b2) * ... am(bm), 其中a为质因子，b为质因子个数
p[N] = N * (a1 - 1) / a1 * (a2 - 1) / a2 * ... * (am - 1) / am
*/
void fun(int n)
{
	p1[1] = 1;
	for(int i = 2; i <= n; i ++)
	{
		if(!st[i])prime[++ cnt] = i, p1[i] = i - 1;
		for(int j = 1; prime[j] * i <= n; j ++)
		{
			st[i * prime[j]] = 1;
			if(i % prime[j] == 0)
			{
				p1[i * prime[j]] = p1[i] * prime[j];
				break;
			}
			p1[i * prime[j]] = p1[i] * (prime[j] - 1);
		}
	}
}
void solve()
{
    LL q;
    cin >> n >> q;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    vector<Info> w(n + 1);
    for(int i = 2; i <= n; i ++)
    {
        if(a[i] < a[i - 1])w[i].g = i - 1;
    }
    LST<Info, Tag> tr(w);
    // for(int i = 1; i <= n; i ++)cout << tr.query(i, i).g << ' ';
    // cout << tr.query(1, n).g << '\n';
    LL g = tr.query(1, n).g;
    cout << g - p1[g] + 1 << '\n';
    while(q --)
    {
        LL p, v;
        cin >> p >> v;
        if(p - 1 > 0){
            if(v < a[p - 1] && a[p] >= a[p - 1])tr.modify(p, p, Tag(p - 1));
            else if(v >= a[p - 1] && a[p] < a[p - 1]) tr.modify(p, p, Tag(0));
        }
        if(p + 1 <= n){
            if(v <= a[p + 1] && a[p] > a[p + 1])tr.modify(p + 1, p + 1, Tag(0));
            else if(v > a[p + 1] && a[p] <= a[p + 1])tr.modify(p + 1, p + 1, Tag(p));
        }
        a[p] = v;
        // for(int i = 1; i <= n; i ++)cout << tr.query(i, i).g << ' ';
        // cout << '\n';
        // cout << tr.query(1, n).g << '\n';
        g = tr.query(1, n).g;
        cout << g - p1[g] + 1 << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    LL _T = 1;
    fun(200000);
    cin >> _T;
    while(_T --)
    {
        solve();
    }
    return 0;
}