#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    vector<int> divs(n + 1);
    for (int i = 1; i <= n; i++) {
      for (int j = i; j <= n; j += i) {
        divs[j] += 1;
      }
    }
    vector<int> st(8 * n);
    function<void(int, int, int, int, int)> Modify = [&](int x, int l, int r, int i, int v) {
      if (l == r) {
        st[x] = v;
        return;
      }
      int mid = l + r >> 1;
      if (i <= mid) {
        Modify(x * 2, l, mid, i, v);
      } else {
        Modify(x * 2 + 1, mid + 1, r, i, v);
      }
      st[x] = __gcd(st[x * 2], st[x * 2 + 1]);
    };
    auto Add = [&](int i, int c) {
      if (a[i] > a[i + 1]) {
        Modify(1, 0, n - 1, i, c * (i + 1));
      }
    };
    for (int i = 0; i + 1 < n; i++) {
      Add(i, 1);
    }
    auto Solve = [&]() {
      int g = st[1];
      if (g == 0) {
        cout << n << '\n';
      } else {
        cout << divs[g] << '\n';
      }
    };
    Solve();
    while (q--) {
      int p, v;
      cin >> p >> v;
      --p;
      for (int i = max(0, p - 1); i < min(n, p + 1); i++) {
        Add(i, 0);
      }
      a[p] = v;
      for (int i = max(0, p - 1); i < min(n, p + 1); i++) {
        Add(i, 1);
      }
      Solve();
    }
  }
  return 0;
}