#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=1e6+5;
int n,a[MAXN];
struct node{int d,id;};
node eat(node x,node y){
	x.d-=y.d;return x;
}
bool operator <(node x,node y){
	if(x.d!=y.d) return x.d<y.d;
	return x.id<y.id;
}
bool operator ==(node x,node y){return x.d==y.d&&x.id==y.id;} 
struct notds{
node q1[MAXN],q2[MAXN];// q1 从小到大，q2 从大到小
int hd1,tl1,hd2,tl2;
notds(){hd1=hd2=1;tl1=tl2=0;}
void push_q1(node x){q1[++tl1]=x;}
void push_q2(node x){q2[++tl2]=x;}
node get_begin(){
	if(hd1>tl1) return q2[tl2];
	if(hd2>tl2) return q1[hd1];
	return min(q1[hd1],q2[tl2]);
} 
node next_begin(){
	if(hd1>tl1) return q2[tl2-1];
	if(hd2>tl2) return q1[hd1+1];
	if(q1[hd1]<q2[tl2]) return (hd1<tl1?min(q1[hd1+1],q2[tl2]):q2[tl2]);
	return (hd2<tl2?min(q1[hd1],q2[tl2-1]):q1[hd1]);
}
node get_end(){
	if(hd1>tl1) return q2[hd2];
	if(hd2>tl2) return q1[tl1];
	return max(q1[tl1],q2[hd2]);
}
void erase(node x){
	if(x==q1[hd1]) hd1++;
	else if(x==q1[tl1]) tl1--;
	else if(x==q2[hd2]) hd2++;
	else if(x==q2[tl2]) tl2++;
	else cerr<<"What do you erase? Baka!"<<endl; 
}
int size(){return tl1-hd1+1+tl2-hd2+1;} 
};
void solve(){
	notds se;
	for(int i=1;i<=n;i++) se.push_q1((node){a[i],i});
	while(se.size()>=2){
		node goal=se.get_end();
		if(se.size()==2||se.next_begin()<eat(goal,se.get_begin())){ 
			goal=eat(goal,se.get_begin());
			se.erase(se.get_begin());se.erase(se.get_end());
			se.push_q2(goal);
		}else break;
	}
	if(se.size()==1) {cout<<1<<endl;return;}
	int now=se.size(),ans=0;
	node bg=se.get_begin();se.erase(bg);
	while(se.size()>=1){
		node goal=se.get_end();
		ans++;
		if(se.size()==1||se.get_begin()<eat(goal,bg)){
			break;
		}else{
			goal=eat(goal,bg);
			se.erase(se.get_end());
			bg=goal;
		}
	}
	cout<<now-(ans&1)<<endl;
}
int main(){
	ios::sync_with_stdio(false);
//	freopen("ex_snakes4.in","r",stdin);
	int _;cin>>_;
	for(int i=1;i<=_;i++){
		if(i==1){
			cin>>n;
			for(int i=1;i<=n;i++) cin>>a[i];
		}else{
			int k;cin>>k;
			for(int i=1,x,y;i<=k;i++){
				cin>>x>>y;a[x]=y;
			}
		}
		solve();
	} 
	return 0;
}