#include <bits/stdc++.h>

using namespace std;

// Store factors of n aside from 1 and n itself
vector<int> factors[200001];


void solve() {
  int n, q; cin >> n >> q;
  
  // Stores index where ai > a(i+1)
  unordered_set<int> s;

  // Stores counter of factors
  unordered_map<int, int> f;

  int arr[n];
  for (int i = 0; i < n; i++)
    cin >> arr[i];

  for (int i = 0; i < n-1; i++) {
    if (arr[i] > arr[i+1]) {
      s.insert(i+1);

      f[i+1]++;
      for (int x : factors[i+1]) {
        f[x]++;
      }
    }
  }

  int sizes = 1;
  // Get possible sizes
  for (int i : factors[*s.begin()]) {
    if (f[i] == s.size())
      sizes++;
  }
  if (f[*s.begin()] == s.size())
    sizes++;

  cout << sizes << '\n';


  int i, x; 
  while (q--) {
    cin >> i >> x;
    // cout << "Current arr: ";
    // for (int i : arr)
    //   cout << i << " ";
    // cout << endl;
    if (s.erase(i-1)) {
      f[i-1]--;
      for (int x : factors[i-1]) f[x]--;
    }
    if (s.erase(i)) {
      f[i]--;
      for(int x : factors[i]) f[x]--;
    }

    arr[i-1] = x;

    if (i != 1 && arr[i-2] > arr[i-1]) {
      s.insert(i-1);
      f[i-1]++;
      for (int x : factors[i-1]) f[x]++;
    }

    if (i != n && arr[i-1] > arr[i]) {
      s.insert(i);
      f[i]++;
      for (int x : factors[i]) f[x]++;
    }

    // cout << "New set: ";
    // for (auto i : s) cout << i << ' ';
    // cout << endl;

    int sizes = 1;
    // Get possible sizes
      // cout << "Factor counts of " << *s.begin() << endl;
    for (int i : factors[*s.begin()]) {
      // cout << i << ' ' << f[i] << endl;
      if (f[i] == s.size())
        sizes++;
    }
    // cout << *s.begin() << ' ' << f[*s.begin()] << endl;
    if (f[*s.begin()] == s.size())
      sizes++;

    cout << sizes << '\n';
  }
}

int main() {
  // Initiate factors
  for (int i = 2; i <= 450; i++) {
    for (int x = pow(i,2); x <= 200000; x++) {
      if (x%i == 0) {
        factors[x].push_back(i);
        if (i != x/i)
          factors[x].push_back(x/i);
      }
    }
  }

  int t; cin >> t;
  while (t--)
    solve();
}