#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
  int n, q;
  cin >> n >> q;
  vector<int> a(n + 2);
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  vector<int> v(n + 2);
  vector<int> gd(4 * n);
  auto build = [&](int pos, int l, int r, auto&& self) -> void {
    if(l == r){
      gd[pos] = v[l];
      return;
    }
    int mid = (l + r) >> 1;
    self(pos << 1, l, mid, self);
    self(pos << 1 | 1, mid + 1, r, self);
    gd[pos] = gcd(gd[pos << 1], gd[pos << 1 | 1]);
    return;
  };
  auto update = [&](int pos, int l, int r, int q, int val, auto&& self) -> void {
    if(l == r){
      gd[pos] = val;
      return;
    }
    int mid = (l + r) >> 1;
    if(q <= mid) 
      self(pos << 1, l, mid, q, val, self);
    else 
      self(pos << 1 | 1, mid + 1, r, q, val, self);
    gd[pos] = gcd(gd[pos << 1], gd[pos << 1 | 1]);
    return;
  };
  for(int i = 1; i <= n; ++i){
    int r = i;
    while(r + 1 <= n && a[r + 1] >= a[r]){
      ++r;
    }
    if(r == n){
      break;
    }
    v[r] = r;
    i = r;
  }
  vector<int> fac(n + 2);
  for(int i = 1; i <= n; ++i){
    for(int j = 1; j * i <= n; ++j){
      ++fac[i * j];
    }
  }
  build(1, 1, n, build);
  cout << fac[gd[1]] << '\n';
  for(int i = 1; i <= q; ++i){
    int pos, val;
    cin >> pos >> val;
    a[pos] = val;
    if(a[pos] > a[pos + 1] && pos + 1 <= n){
      update(1, 1, n, pos, pos, update);
    }
    else if(pos + 1 <= n){
      update(1, 1, n, pos, 0, update);
    }
    if(a[pos - 1] > a[pos] && pos - 1 >= 1){
      update(1, 1, n, pos - 1, pos - 1, update);
    }
    else if(pos - 1 >= 1){
      update(1, 1, n, pos - 1, 0, update);
    }
    cout << fac[gd[1]] << '\n';
  }
}


int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int t; t = 1;
  cin >> t;
  while(t--)solve();
}