#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cassert>
#include <cctype>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <sstream>
#include <complex>
#include <fstream>
#include <functional>
#include <numeric>
#include <utility>
#include <algorithm>
#include <assert.h>
using namespace std;
#define endl '\n'
#define MOD 1000000007ULL
#define INF 1000000000
#define eps 1e-8
#define ll long long
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define debug(X) cerr << " --> " << #X << " = " << X << endl
#define sd(x) scanf("%d",&(x))
#define slld(x) scanf("%lld",&(x))
#define pd(x) printf("%d\n",(x))
#define plld(x) printf("%lld\n",(x))
#define gcd __gcd
#define csl ios_base::sync_with_stdio(false); cin.tie(NULL)
typedef vector< vector<int> > vvi;
typedef vector< vector<ll> > vvl;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
int st[400005];
int lazy[400005];
int a[100005];
void construct(int node, int i, int j)
{
if(i == j)
{
st[node] = a[i];
lazy[node] = -1;
return;
}
int mid = (i+j)/2;
construct(node*2, i, mid);
construct(node*2+1,mid+1,j);
st[node] = st[node*2]+st[node*2+1];
lazy[node] = -1;
return;
}
void push(int node, int i, int j)
{
if(lazy[node] != -1)
{
st[node] = (j-i+1)*lazy[node];
if(i != j)
{
lazy[node*2] = lazy[node];
lazy[node*2+1] = lazy[node];
}
lazy[node] = -1;
}
}
void update(int node, int i, int j, int x, int y, int v)
{
if(i > j) return;
push(node, i, j);
if(j < x || i > y) return;
if(i >= x && j <= y)
{
st[node] = (j-i+1)*v;
if(i != j)
{
lazy[node*2] = v;
lazy[node*2+1] = v;
}
return;
}
int mid = (i+j)/2;
update(node*2, i, mid, x, y, v);
update(node*2+1, mid+1, j, x, y, v);
st[node]=st[node*2]+st[node*2+1];
return;
}
int query(int node, int i, int j, int x, int y)
{
if(i > j) return 0;
push(node, i, j);
if(j < x || i > y) return 0;
if(i >= x && j <= y)
return st[node];
int mid = (i+j)/2;
return query(node*2, i, mid, x, y)+query(node*2+1, mid+1, j, x, y);
}
int main()
{
csl;
int t;
cin >> t;
while(t--)
{
string s;
cin >> s;
for(int i = 0;i < s.size();i++)
{
if(s[i] == 'X')
a[i+1] = 1;
else a[i+1] = 0;
}
int n = s.size();
construct(1, 1, n);
int k;
cin >> k;
int aq,l,r;
while(k--)
{
cin >> aq >> l >> r;
if(aq == 1)
{
update(1, 1, n, l, r, 1);
}
else
{
update(1, 1, n, l, r, 0);
}
}
for(int i = 1;i <= n;i++)
a[i] = query(1, 1, n, i, i);
int pre[n+1], suf[n+1];
pre[0] = 0;
pre[1] = a[1];
suf[n] = a[n];
for(int i = 2;i <= n;i++)
{
pre[i] = pre[i-1] + a[i];
suf[n-i+1] = suf[n-i+2] + a[n-i+1];
}
int ans = min(pre[n], n-pre[n]);
for(int i = 1;i < n;i++)
{
ans = min(ans, i-pre[i]+suf[i+1]);
}
cout << ans << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxjc3RkbGliPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxjbWF0aD4KI2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDxjY3R5cGU+CiNpbmNsdWRlIDxjbGltaXRzPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxzdGFjaz4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPGRlcXVlPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8bGlzdD4KI2luY2x1ZGUgPGl0ZXJhdG9yPgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPGNvbXBsZXg+CiNpbmNsdWRlIDxmc3RyZWFtPgojaW5jbHVkZSA8ZnVuY3Rpb25hbD4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8YXNzZXJ0Lmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBlbmRsICdcbicKI2RlZmluZSBNT0QgMTAwMDAwMDAwN1VMTAojZGVmaW5lIElORiAxMDAwMDAwMDAwCiNkZWZpbmUgZXBzIDFlLTgKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBGIGZpcnN0CiNkZWZpbmUgUyBzZWNvbmQKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBkZWJ1ZyhYKSBjZXJyIDw8ICIgLS0+ICIgPDwgI1ggPDwgIiA9ICIgPDwgWCA8PCBlbmRsCiNkZWZpbmUgc2QoeCkgc2NhbmYoIiVkIiwmKHgpKQojZGVmaW5lIHNsbGQoeCkgc2NhbmYoIiVsbGQiLCYoeCkpCiNkZWZpbmUgcGQoeCkgcHJpbnRmKCIlZFxuIiwoeCkpCiNkZWZpbmUgcGxsZCh4KSBwcmludGYoIiVsbGRcbiIsKHgpKQojZGVmaW5lIGdjZCBfX2djZAojZGVmaW5lIGNzbCBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsgY2luLnRpZShOVUxMKQoKdHlwZWRlZiB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gdnZpOwp0eXBlZGVmIHZlY3RvcjwgdmVjdG9yPGxsPiA+IHZ2bDsKdHlwZWRlZiBwYWlyPGludCwgaW50PiBwaWk7CnR5cGVkZWYgcGFpcjxsb25nIGxvbmcsIGxvbmcgbG9uZz4gcGxsOwp0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpOwp0eXBlZGVmIHZlY3RvcjxsbD4gdmxsOwoKaW50IHN0WzQwMDAwNV07CmludCBsYXp5WzQwMDAwNV07CmludCBhWzEwMDAwNV07Cgp2b2lkIGNvbnN0cnVjdChpbnQgbm9kZSwgaW50IGksIGludCBqKQp7CglpZihpID09IGopCgl7CgkJc3Rbbm9kZV0gPSBhW2ldOwoJCWxhenlbbm9kZV0gPSAtMTsKCQlyZXR1cm47Cgl9CglpbnQgbWlkID0gKGkraikvMjsKCWNvbnN0cnVjdChub2RlKjIsIGksIG1pZCk7Cgljb25zdHJ1Y3Qobm9kZSoyKzEsbWlkKzEsaik7CglzdFtub2RlXSA9IHN0W25vZGUqMl0rc3Rbbm9kZSoyKzFdOwoJbGF6eVtub2RlXSA9IC0xOwoJcmV0dXJuOwp9Cgp2b2lkIHB1c2goaW50IG5vZGUsIGludCBpLCBpbnQgaikKewoJaWYobGF6eVtub2RlXSAhPSAtMSkKCXsKCQlzdFtub2RlXSA9IChqLWkrMSkqbGF6eVtub2RlXTsKCQlpZihpICE9IGopCgkJewoJCQlsYXp5W25vZGUqMl0gPSBsYXp5W25vZGVdOwoJCQlsYXp5W25vZGUqMisxXSA9IGxhenlbbm9kZV07CgkJfQoJCWxhenlbbm9kZV0gPSAtMTsKCX0KfQoKdm9pZCB1cGRhdGUoaW50IG5vZGUsIGludCBpLCBpbnQgaiwgaW50IHgsIGludCB5LCBpbnQgdikKewoJaWYoaSA+IGopIHJldHVybjsKCXB1c2gobm9kZSwgaSwgaik7CglpZihqIDwgeCB8fCBpID4geSkgcmV0dXJuOwoJaWYoaSA+PSB4ICYmIGogPD0geSkKCXsKCQlzdFtub2RlXSA9IChqLWkrMSkqdjsKCQlpZihpICE9IGopCgkJewoJCQlsYXp5W25vZGUqMl0gPSB2OwoJCQlsYXp5W25vZGUqMisxXSA9IHY7CgkJfQoJCXJldHVybjsKCX0KCWludCBtaWQgPSAoaStqKS8yOwoJdXBkYXRlKG5vZGUqMiwgaSwgbWlkLCB4LCB5LCB2KTsKCXVwZGF0ZShub2RlKjIrMSwgbWlkKzEsIGosIHgsIHksIHYpOwoJc3Rbbm9kZV09c3Rbbm9kZSoyXStzdFtub2RlKjIrMV07CglyZXR1cm47Cn0KCmludCBxdWVyeShpbnQgbm9kZSwgaW50IGksIGludCBqLCBpbnQgeCwgaW50IHkpCnsKCWlmKGkgPiBqKSByZXR1cm4gMDsKCXB1c2gobm9kZSwgaSwgaik7CglpZihqIDwgeCB8fCBpID4geSkgcmV0dXJuIDA7CglpZihpID49IHggJiYgaiA8PSB5KQoJCXJldHVybiBzdFtub2RlXTsKCWludCBtaWQgPSAoaStqKS8yOwoJcmV0dXJuIHF1ZXJ5KG5vZGUqMiwgaSwgbWlkLCB4LCB5KStxdWVyeShub2RlKjIrMSwgbWlkKzEsIGosIHgsIHkpOwp9CgppbnQgbWFpbigpCnsKCWNzbDsKCglpbnQgdDsKCWNpbiA+PiB0OwoJd2hpbGUodC0tKQoJewoJCXN0cmluZyBzOwoJCWNpbiA+PiBzOwoJCWZvcihpbnQgaSA9IDA7aSA8IHMuc2l6ZSgpO2krKykKCQl7CgkJCWlmKHNbaV0gPT0gJ1gnKQoJCQkJYVtpKzFdID0gMTsKCQkJZWxzZSBhW2krMV0gPSAwOwoJCX0KCQlpbnQgbiA9IHMuc2l6ZSgpOwoJCWNvbnN0cnVjdCgxLCAxLCBuKTsKCQlpbnQgazsKCQljaW4gPj4gazsKCQlpbnQgYXEsbCxyOwoJCXdoaWxlKGstLSkKCQl7CgkJCWNpbiA+PiBhcSA+PiBsID4+IHI7CgkJCWlmKGFxID09IDEpCgkJCXsKCQkJCXVwZGF0ZSgxLCAxLCBuLCBsLCByLCAxKTsKCQkJfQoJCQllbHNlCgkJCXsKCQkJCXVwZGF0ZSgxLCAxLCBuLCBsLCByLCAwKTsKCQkJfQoJCX0KCQlmb3IoaW50IGkgPSAxO2kgPD0gbjtpKyspCgkJCWFbaV0gPSBxdWVyeSgxLCAxLCBuLCBpLCBpKTsKCQlpbnQgcHJlW24rMV0sIHN1ZltuKzFdOwoJCXByZVswXSA9IDA7CgkJcHJlWzFdID0gYVsxXTsKCQlzdWZbbl0gPSBhW25dOwoJCWZvcihpbnQgaSA9IDI7aSA8PSBuO2krKykKCQl7CgkJCXByZVtpXSA9IHByZVtpLTFdICsgYVtpXTsKCQkJc3VmW24taSsxXSA9IHN1ZltuLWkrMl0gKyBhW24taSsxXTsKCQl9CgkJaW50IGFucyA9IG1pbihwcmVbbl0sIG4tcHJlW25dKTsKCQlmb3IoaW50IGkgPSAxO2kgPCBuO2krKykKCQl7CgkJCWFucyA9IG1pbihhbnMsIGktcHJlW2ldK3N1ZltpKzFdKTsKCQl9CgkJY291dCA8PCBhbnMgPDwgZW5kbDsKCX0KCglyZXR1cm4gMDsKfQ==