#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+5;
inline int read(){
	int p=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') p=(p<<1)+(p<<3)+ch-'0',ch=getchar();return p;
}
struct node{
	int x,y;
	bool operator <(const node &p)const{
		if(x!=p.x) return x<p.x;
		return y<p.y;
	}
};
struct node1{
	int x,y;
	bool operator <(const node1 &p)const{
		if(x!=p.x) return x>p.x;
		return y>p.y;
	}
};
int t,a[N],cnt,n,k;
priority_queue<node> q1;
priority_queue<node1> q2;
int main(){
//	freopen("snakes1.in","r",stdin);
//	freopen("snakes.out","w",stdout);
	t=read();
	while(t--){
		cnt++;
		if(cnt==1){
			n=read();
			for(int i=1;i<=n;i++) a[i]=read();
		}
		else{
			k=read();
			while(k--){
				int x,y;
				x=read(),y=read();
				a[x]=y;
			}
		}
		while(q1.size()) q1.pop();
		while(q2.size()) q2.pop();
		for(int i=1;i<=n;i++){
			q1.push({a[i],i});
			q2.push({a[i],i});
		}
		int now=n+1;
		while(1){
			now--;
			if(now==2){
				printf("1\n");
				break;
			} 
			int o=q1.top().x,p=q2.top().x;  //   值 
			int id1=q1.top().y,id2=q2.top().y;  //  位置 
			
			//q1 big  q2 small 
			q1.pop();q2.pop();
			if(o-p<q2.top().x||(o-p==q2.top().x&&id1<q2.top().y)){
				if(now%2==1){
					printf("%d\n",now);
					break;
				}
				else{
					q1.push({o-p,id1});
					q2.push({o-p,id1});
				}
			}
			else{
				q1.push({o-p,id1});
				q2.push({o-p,id1});
			}
		}
	}
	return 0;
}