1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cassert>
 5 using namespace std;
 6 const int N = 100005;
 7 template <typename T> inline void chkmax(T &a,T b){if(a<b) a=b;}
 8 int seg[N<<2][2][2], side[N<<2][2], mx[N<<2][2], full[N<<2][2],chg[N<<2];
 9 int upt(int pos){
10     for(int i=0;i<2;i++) side[pos][i] = 9- side[pos][i];
11     swap(mx[pos][0],mx[pos][1]);
12     swap(full[pos][0],full[pos][1]);
13     for(int i=0;i<2;i++){
14         swap(seg[pos][0][i],seg[pos][1][i]);
15     }
16 }
17 void pushdown(int pos,int L,int R){
18     if(chg[pos]){
19         upt(pos);
20         chg[pos] = 0;
21         if(L==R) return ;
22         chg[pos<<1] ^=1;
23         chg[pos<<1|1]^=1;
24     }
25 }
26 void sumup(int pos,int L,int R){
27     int mid = L+R >>1;
28     pushdown(pos<<1 , L, mid);
29     pushdown(pos<<1|1,mid+1,R);
30     side[pos][0] = side[pos<<1][0];
31     side[pos][1] = side[pos<<1|1][1];
32     full[pos][0] = full[pos<<1][0] && full[pos<<1|1][0] && side[pos<<1][1] <= side[pos<<1|1][0];
33     full[pos][1] = full[pos<<1][1] && full[pos<<1|1][1] && side[pos<<1][1] >= side[pos<<1|1][0];
34     seg[pos][0][0] = seg[pos<<1][0][0] + (full[pos<<1][0] && side[pos<<1][1] <= side[pos<<1|1][0] ? seg[pos<<1|1][0][0] : 0);
35     seg[pos][1][0] = seg[pos<<1][1][0] + (full[pos<<1][1] && side[pos<<1][1] >= side[pos<<1|1][0] ? seg[pos<<1|1][1][0] : 0);
36     seg[pos][0][1] = seg[pos<<1|1][0][1] + (full[pos<<1|1][0] && side[pos<<1][1] <= side[pos<<1|1][0] ? seg[pos<<1][0][1] : 0);
37     seg[pos][1][1] = seg[pos<<1|1][1][1] + (full[pos<<1|1][1] && side[pos<<1][1] >= side[pos<<1|1][0] ? seg[pos<<1][1][1] : 0);
38 //    cout<<seg[pos][0][1]<<" "<<seg[pos<<1][0][1]<<" "<<seg[pos<<1|1][0][1]<<" "<<full[pos<<1|1]
39     for(int i=0;i<2;i++){
40         mx[pos][i] = max(seg[pos][i][0],seg[pos][i][1]);
41         chkmax(mx[pos][i], max(mx[pos<<1][i] , mx[pos<<1|1][i]) );
42         if( i ? side[pos<<1][1] >= side[pos<<1|1][0]:side[pos<<1][1] <= side[pos<<1|1][0])
43         chkmax(mx[pos][i], seg[pos<<1][i][1] + seg[pos<<1|1][i][0]);
44     }
45 }
46 char num[N];
47 int last;
48 void update(int l,int r,int pos,int L,int R,int flag){
49     if(l<=L && r>=R){
50         if(flag){
51             chg[pos] ^=1;
52         }
53         else {
54             side[pos][0] = side[pos][1] = num[last++] - '0';
55             mx[pos][0] = mx[pos][1] = full[pos][0] = full[pos][1] = 1;
56             for(int i=0;i<2;i++) for(int j=0;j<2;j++) seg[pos][i][j] =1;
57         }
58         return ;
59     }
60     pushdown(pos,L,R);
61     int mid = L+ R >>1;
62     if(l<=mid) update(l,r,pos<<1, L, mid, flag);
63     if(r > mid)update(l,r,pos<<1|1,mid+1,R, flag);
64     sumup(pos,L,R);
65 //    cout<<L<<" "<<R<<" "<<seg[pos][0][1]<<" "<<mx[pos][0]<<endl;
66 }
67 int main(){
68     int t;
69     scanf("%d",&t);
70     while(t--){
71         int n,m;last = 0;
72         scanf("%d%d",&n,&m);
73         scanf("%s",num);
74         memset(chg,0,sizeof(chg));
75         for(int i=0;i<n;i++){
76             update(i,i,1,0,n-1,0);
77         }
78         assert(last==n);
79         char cmd[10];
80         while(m--){
81             scanf("%s",cmd);
82             if(cmd[0]=='q'){
83                 pushdown(1,0,n-1);
84                 printf("%d\n",mx[1][0]);
85             }
86             else {
87                 int l,r;
88                 scanf("%d%d",&l,&r);
89                 l--;r--;
90                 update(l,r,1,0,n-1,1);
91             }
92         }
93         puts("");
94     }
95     return 0;
96 }
97