1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>

using namespace std;


int main(){
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
	int ti;cin>>ti;
	while(ti--){
		int n;cin>>n;
		multiset <pair<int,int> >s;
		long long Q=0;int akt=0;
		char x;
		for(int i=0;i<n;i++){
			cin>>x;int I=i;
			while(x=='0'){
				i++;
				if(i==n)break;
				cin>>x;
			}
			if(Q==0 and i<n){
				if(i>I){
					s.insert({2*(i-I),2});
					akt++;
				}
				Q++;
			}
			else if(i<n){
				Q++;
				if(i>I){
					s.insert({i-I,1});
					akt+=2;
				}
			}
			else if(i==n){
				s.insert({2*(i-I),2});
				akt++;
			}
		}
			/*for(auto it=s.begin();it!=s.end();it++){
				pair<int,int> p=*it;
				cout<<p.first<<" "<<p.second<<"\n";
				
			}*/
		int t=0;
		while(!s.empty()){
			auto qu=(--s.end());
			pair<int,int> p=*(--s.end());
			s.erase(qu);
			if(p.second==1){
				p.first-=t+1;p.first*=2;
				p.second=2;
				if(p.first>2*t)s.insert(p);
				else akt--;
				akt--;
			}
			else{
				akt--;
			}
			t++;Q+=akt;
			if(!s.empty()){
				for(auto it=s.begin();it!=s.end();){
					p=*it;auto qu=it++;
					if(p.first>2*t)break;
					else if(p.first==2*t){
						s.erase(qu);
						if(p.second==2)akt--;
						else akt-=2;
					}
					else if(p.first==2*t-1){
						Q--;akt-=2;s.erase(qu);
					}
					
				}
			}
		}
		cout<<Q<<"\n";
		
	}
	
	
	

return 0;
}