#include <bits/stdc++.h>
using namespace std;
int d[4*300005];
int a[300005];
int b[4*300005];
bool v[4*300005];
int yin[200005];
void build(int s, int t, int p) {
  // 对 [s,t] 区间建立线段树,当前根的编号为 p
  if (s == t) {
    d[p] = a[s];
    return;
  }
  int m = s + ((t - s) >> 1);
  // 移位运算符的优先级小于加减法，所以加上括号
  // 如果写成 (s + t) >> 1 可能会超出 int 范围
  build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
  // 递归对左右区间建树
  d[p] = d[p * 2] + d[(p * 2) + 1];
}
void update2(int l, int r, int c, int s, int t, int p) {
  if (l <= s && t <= r) {
    d[p] = (t - s + 1) * c, b[p] = c, v[p] = 1;
    return;
  }
  int m = s + ((t - s) >> 1);
  // 额外数组储存是否修改值
  if (v[p]) {
    d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m);
    b[p * 2] = b[p * 2 + 1] = b[p];
    v[p * 2] = v[p * 2 + 1] = 1;
    v[p] = 0;
  }
  if (l <= m) update2(l, r, c, s, m, p * 2);
  if (r > m) update2(l, r, c, m + 1, t, p * 2 + 1);
  d[p] = d[p * 2] + d[p * 2 + 1];
}
int getgcd2(int l, int r, int s, int t, int p) {
  if (l <= s && t <= r) return d[p];
  int m = s + ((t - s) >> 1);
  if (v[p]) {
    d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m);
    b[p * 2] = b[p * 2 + 1] = b[p];
    v[p * 2] = v[p * 2 + 1] = 1;
    v[p] = 0;
  }
  int gcd = 0;
  if (l <= m) gcd = getgcd2(l, r, s, m, p * 2);
  if (r > m) gcd = __gcd(gcd , getgcd2(l, r, m + 1, t, p * 2 + 1) );
  return gcd;
}
int main()
{
    for(int j=1;j<=200005;j++)
    {
        int sum=0;
        int N=j;
        for (int i = 2; i  <= N /i; i++)
        {
            if (N % i == 0)
            {                          
              while (N % i == 0) N /= i;// 如果 i 能够整除 N，说明 i 为 N 的一个质因子。
              sum++;
            }
        }
        if (N != 1) sum++; // 说明再经过操作之后 N 留下了一个素数
        yin[j]=sum;
    }
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        vector <int> w(n,0);
        for(int i=0;i<n;i++) cin>>w[i];
        a[1]=0;cout<<a[1]<<' ';
        for(int i=1;i<n;i++)
        {
            if(w[i-1]>w[i]) a[i+1]=i;
            else a[i+1]=0;
            cout<<a[i+1]<<' ';
        }
        cout<<'\n';
        build(1,n,1);
        cout<<"gcd="<<getgcd2(1,n,1,n,1)<<'\n';
        int q;cin>>q;
        while(q--)
        {
            int index,x;cin>>index>>x;
            w[index-1]=x;
            if(index>1)
            {
                if(w[index-2]>w[index-1]) update2(index-1,index-1,index-1,1,n,1);
            }
            if(index<n)
            {
                if(w[index-1]>w[index]) update2(index,index,index,1,n,1);
            }
            cout<<'\n'<<"gcd="<<getgcd2(1,n,1,n,1)<<'\n';
        }
    }
    return 0;
}