#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;
}
void solve(){
	set<node> se;
	for(int i=1;i<=n;i++) se.insert((node){a[i],i});
	while(se.size()>=2){
		node goal=*(--se.end());
		if(se.size()==2||*(++se.begin())<eat(goal,*se.begin())){
			goal=eat(goal,*se.begin());
			se.erase(se.begin());se.erase(--se.end());
			se.insert(goal);
		}else break;
	}
	if(se.size()==1) {cout<<1<<endl;return;}
	int now=se.size(),ans=0;
	while(se.size()>=2){
		node goal=*(--se.end());
		ans++;
		if(se.size()==2||*(++se.begin())<eat(goal,*se.begin())){
			break;
		}else{
			goal=eat(goal,*se.begin());
			se.erase(se.begin());se.erase(--se.end());
			se.insert(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;
}