Untitled

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define e7na_leeh ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0);
using namespace std;
string di[] = {"L", "R", "U", "D", "UR", "UL", "DR", "DL"};
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {-1, 1, 0, 0, 1, -1, 1, -1};
const ll N = 1e5 + 5, mod = 1e9 + 7, inf = 1e18;
ll n,ct=0; string s;
vector<ll>v[26],fre(26);
void add(ll ix,char c){
    for (char i = 'a'; i <c ; ++i) {
        if(v[i-'a'].empty()||v[i-'a'].back()<ix)
            continue;
        auto it= lower_bound(all(v[i-'a']),ix)-v[i-'a'].begin();
        ct+=sz(v[i-'a'])-it;
    }
    for (char i = c+1; i <='z' ; ++i) {
        if(v[i-'a'].empty()||v[i-'a'][0]>ix)
            continue;
        auto it= lower_bound(all(v[i-'a']),ix)-v[i-'a'].begin();
        ct+=it;
    }
}
void del(ll ix,char c){
    for (char i = 'a'; i <c ; ++i) {
        if(v[i-'a'].empty()||v[i-'a'].back()<ix)
            continue;
        auto it= lower_bound(all(v[i-'a']),ix)-v[i-'a'].begin();
        ct-=sz(v[i-'a'])-it;
    }
    for (char i = c+1; i <='z' ; ++i) {
        if(v[i-'a'].empty()||v[i-'a'][0]>ix)
            continue;
        auto it= lower_bound(all(v[i-'a']),ix)-v[i-'a'].begin();
        ct-=it;
    }

}
void solve() {
    cin>>n>>s;
    for (int i = 0; i <n ; ++i) {
        v[s[i]-'a'].push_back(i);
        for (char j = s[i]+1; j <='z' ; ++j) {
            ct+=fre[j-'a'];
        }
        fre[s[i]-'a']++;
    }
    ll q; cin>>q;
    while(q--){
        ll typ; cin>>typ;

        if(typ==1){
            ll ix; char c; cin>>ix>>c;
            --ix;
            if(s[ix]==c) continue;
            del(ix,s[ix]);
            auto it= lower_bound(all(v[s[ix]-'a']),ix);
            v[s[ix]-'a'].erase(it);
            s[ix]=c;
            if(v[c-'a'].empty()||v[c-'a'].back()<ix){
                v[c-'a'].push_back(ix);
            }
            else {
                it = lower_bound(all(v[c - 'a']), ix);
                v[c - 'a'].insert(it, ix);
            }
            add(ix,c);
        }

        else if(typ==2){
            ll l,r; cin>>l>>r; --l,--r;
            if(s[l]==s[r]) continue;
            auto it= lower_bound(all(v[s[l]-'a']),l);
            v[s[l]-'a'].erase(it);
            if(v[s[l]-'a'].empty()||v[s[l]-'a'].back()<r){
                v[s[l]-'a'].push_back(r);
            }
            else {
                it = lower_bound(all(v[s[l] - 'a']), r);
                v[s[l] - 'a'].insert(it, r);
            }
            it= lower_bound(all(v[s[r]-'a']),r);
            v[s[r]-'a'].erase(it);
            if(v[s[r]-'a'].empty()||v[s[r]-'a'].back()<l){
                v[s[r]-'a'].push_back(l);
            }
            else {
                it = lower_bound(all(v[s[r] - 'a']), l);
                v[s[r] - 'a'].insert(it, l);
            }
            del(l,s[l]);
            del(r,s[r]);
            swap(s[l],s[r]);
            add(l,s[l]);
            add(r,s[r]);
        }
        else{
            cout<<ct<<'\n';
        }
    }
    ct=0;
    for (int i = 0; i <26 ; ++i) {
        fre[i]=0;
        v[i].clear();
    }

}
int main() {
    e7na_leeh
    int testCases = 1;
    cin >> testCases;
    while (testCases--) solve();


    return 0;
}