#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 100;
template<typename Info>
struct SegmentTree {
    int n;
    vector<Info> info;
    SegmentTree() :n(1) {}
    SegmentTree(int _n) :info((_n + 1) * 4 , Info()) , n(_n) {
        build(1 , 1 , _n , Info());
    }
    SegmentTree(int _n , const Info& _k) :info((_n + 1) * 4 , Info()) , n(_n) {
        build(1 , 1 , _n , _k);
    }
    SegmentTree(int _n , vector<Info> _init) :info((_n + 1) * 4 , Info()) , n(_n) {
        build(1 , 1 , _n , _init);
    }
    void pushup(int p) {
        info[p] = info[p << 1] + info[p << 1 | 1];
    }
    void build(int p , int l , int r , vector<Info>& _init)
    {
        info[p] = _init[l];
        if (l == r)
            return;
        int mid = l + r >> 1;
        build(p << 1 , l , mid , _init);
        build(p << 1 | 1 , mid + 1 , r , _init);
        pushup(p);
    }
    void build(int p , int l , int r , const Info& k)
    {
        info[p] = k;
        if (l == r)
            return;
        int mid = l + r >> 1;
        build(p << 1 , l , mid , k);
        build(p << 1 | 1 , mid + 1 , r , k);
        pushup(p);
    }
    void modify(int p , int L , int R , int x , const Info& k) {
        if (L == R) {
            info[p] = k;
            return;
        }
        int mid = L + R >> 1;
        if (x <= mid) modify(p << 1 , L , mid , x , k);
        else modify(p << 1 | 1 , mid + 1 , R , x , k);
        pushup(p);
    }
    void modify(int x , const Info& k) {
        modify(1 , 1 , n , x , k);
    }
    Info query(int p , int L , int R , int l , int r) {
        if (l > R || r < L) {
            return Info();
        }
        if (l <= L && R <= r) {
            return info[p];
        }
        int mid = L + R >> 1;
        return query(p << 1 , L , mid , l , r) + query(p << 1 | 1 , mid + 1 , R , l , r);
    }
    Info query(int l , int r) {
        return query(1 , 1 , n , l , r);
    }
};
struct Info {
    int val = 0;
};
Info operator+(const Info& a , const Info& b) {
    return Info{ __gcd(a.val,b.val) };
}
int a[200005];
vector<int> p[N];
void init() {
    for (int i = 1;i <= 2e5;i++) {
        for (int j = 1;j * i <= 2e5;j++) {
            p[i * j].push_back(i);
        }
    }
}
void solve() {
    int n , q;
    cin >> n >> q;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    a[n + 1] = 0x7f7f7f7f;
    SegmentTree<Info> sg(n , Info());
    for (int i = 1;i < n;i++) {
        if (a[i] > a[i + 1]) {
            sg.modify(i , Info{ i });
        }
    }
    cout << p[sg.query(1 , n).val].size() << endl;
    while (q--) {
        int x , v;
        cin >> x >> v;
        if (x - 1 > 0)sg.modify(x - 1 , Info{ 0 });
        sg.modify(x , Info{ 0 });
        a[x] = v;
        if (a[x] > a[x + 1]) {
            sg.modify(x , Info{ x });
        }
        if (a[x - 1] > a[x]) {
            sg.modify(x - 1 , Info{ x - 1 });
        }
        cout << p[sg.query(1 , n).val].size() << endl;
    }
}
signed main() {
    init();
    int t = 1;
    cin >> t;
    while (t--) solve();

}