#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
 
        int n;
        string s;
        cin >> n >> s;
 
        int ans = 0;
 
        string p = s;
        sort(p.begin(), p.end());
 
        for(int i = 0; i < n; i++) if(s[i] != p[i]) ans++;
 
        cout << ans / 2 << '\n';
 
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int t;
    cin >> t;
    while(t--){
        int x;
        cin >> x;
        cout << 2*x<< '\n';
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
 
        int n;
        cin >> n;
 
        vector<long long> a(n);
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
 
        ll ans = 0;
        for(int i = 0; i < n; i++){
            if(i % 2) ans -= a[i];
            else ans += a[i];
        }
 
        ll init = ans;
 
        for(int i = 0; i < n; i++) ans = max(ans, init + i - (i % 2));
 
        ll min_even = LLONG_MAX / 2, min_odd = LLONG_MAX / 2;
        for(int i = 0; i < n; i++){
            if(i % 2){
                ans = max(init + i + a[i] + a[i] - min_even, ans);
                min_odd = min(min_odd, i - a[i] - a[i]);
            }
            else{
                ans = max(init + i - a[i] - a[i] - min_odd, ans);
                min_even = min(min_even, i + a[i] + a[i]);
            }
        }
 
        cout << ans << '\n';
 
    }
 
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

#define fo(i, a, b) for (ll i = a; i < b; i++)
#define F first
#define S second
#define pb push_back
#define mp make_pair
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    ll T, n;
    cin >> T;
    while (T--) {
        cin >> n;
        vector<pl> a(n);
        fo(i, 0, n)cin >> a[i].first >> a[i].second;
        ll ans = 0;
        fo(i, 0, n)ans += a[i].second - a[i].first + 1;
        ans += n / 2;
        vector<pair<ll, pl>> b(n);
        fo(i, 0, n) {
            b[i].second = a[i];
            b[i].first = a[i].first + a[i].second;
        }
        sort(b.begin(), b.end());
        if (n % 2 == 0) {
            fo(i, 0, n) {
                ans += a[i].second;
            }
            fo(i, 0, n / 2) {
                ans -= b[i].first;
            }
            cout << ans - n - n / 2 << "\n";
        }
        else {
            ll k = 0, w = 0;
            fo(i, 0, n) {
                w += a[i].second;
            }
            fo(i, 0, n / 2+1) {
                w-= b[i].first;
            }
            fo(i, 0, n / 2 + 1) {
                k = max(k, w + b[i].S.F);
            }
            w += b[n / 2].first;
            fo(i, n / 2 + 1, n) {
                k = max(k, w - b[i].S.S);
            }
            cout << ans + k  - n - n / 2 << "\n";
        }
    }
}

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
int removebit(int n, int bit)
{
    int msk = (1 << 22);
    int filtermask = msk - (1 << bit);
    return ((n >> 1) & filtermask) | (n & ((1 << bit) - 1));
}
const ll MOD = 1e9+7;
class mint
{
public:
    ll val;
    static ll mod_exp(ll a, ll b)
    {
        ll res = 1;
        a = a % MOD;
        while (b > 0)
        {
            if (b % 2 == 1)
                res = (res * a) % MOD;
            b /= 2;
            a = (a * a) % MOD;
        }
        return res;
    }
    static ll gcdExtended(ll a, ll b, ll *x, ll *y)
    {
        if (a == 0)
        {
            *x = 0, *y = 1;
            return b;
        }
        ll x1, y1;
        ll gcd = gcdExtended(b % a, a, &x1, &y1);
        *x = y1 - (b / a) * x1;
        *y = x1;
        return gcd;
    }
    static ll modInverse(ll a)
    {
        ll x, y;
        ll g = gcdExtended(a, MOD, &x, &y);
        g++;
        ll res = (x % MOD);
        if (res < 0)
            res += MOD;
        return res;
    }
    mint() { val = 0; }
    mint(ll x)
    {
        val = x % MOD;
        if (val < 0)
            val += MOD;
    }
    mint &operator+=(const mint &other)
    {
        val += other.val;
        if (val >= MOD)
            val -= MOD;
        return (*this);
    }
    mint &operator-=(const mint &other)
    {
        val -= other.val;
        if (val < 0)
            val += MOD;
        return (*this);
    }
    mint &operator*=(const mint &other)
    {
        val = (val * other.val) % MOD;
        return (*this);
    }
    mint &operator/=(const mint &other)
    {
        val = (val * modInverse(other.val)) % MOD;
        return (*this);
    }
    mint &operator=(const mint &other)
    {
        val = other.val;
        return (*this);
    }
    mint operator+(const mint &other) const { return mint(*this) += other; }
    mint operator-(const mint &other) const { return mint(*this) -= other; }
    mint operator*(const mint &other) const { return mint(*this) *= other; }
    mint operator/(const mint &other) const { return mint(*this) /= other; }
    bool operator==(const mint &other) const { return val == other.val; }
 
    mint operator++()
    {
        ++val;
        if (val == MOD)
            val = 0;
        return (*this);
    }
    mint operator++(int)
    {
        val++;
        if (val == MOD)
            val = 0;
        return mint(val - 1);
    }
    mint operator--()
    {
        --val;
        if (val == -1)
            val = MOD - 1;
        return (*this);
    }
    mint operator--(int)
    {
        val--;
        if (val == -1)
            val = MOD - 1;
        return mint(val + 1);
    }
 
    // ^ has very low precedence, careful!!
 
    template <typename T>
    mint &operator^=(const T &other)
    {
        val = mod_exp(val, other);
        return (*this);
    }
    template <typename T>
    mint operator^(const T &other) const { return mint(*this) ^= other; }
 
    mint &operator^=(const mint &other)
    {
        val = mod_exp(val, other.val);
        return (*this);
    }
    mint operator^(const mint &other) const { return mint(*this) ^= other; }
 
    template <typename T>
    explicit operator T() { return (T)val; }
    template <typename T>
    friend mint operator+(T other, const mint &M) { return mint(other) + M; }
    template <typename T>
    friend mint operator-(T other, const mint &M) { return mint(other) - M; }
    template <typename T>
    friend mint operator*(T other, const mint &M) { return mint(other) * M; }
    template <typename T>
    friend mint operator/(T other, const mint &M) { return mint(other) / M; }
    template <typename T>
    friend mint operator^(T other, const mint &M) { return mint(other) ^ M; }
 
    friend std::ostream &operator<<(std::ostream &output, const mint &M) { return output << M.val; }
    friend std::istream &operator>>(std::istream &input, mint &M)
    {
        input >> M.val;
        M.val %= MOD;
        return input;
    }
};
 
const int maxn = 20;
const int maxm = 30;
 
ll modpow(ll a , ll b ) {
    ll res = 1 ;
    a %= MOD;
    while( b > 0 ) {
        if( b&1 ) res = ( res*a ) % MOD;
        a = ( a*a ) % MOD;
        b >>= 1 ;
    }
    return res ;
}
 
int main()
{   int t;
    cin >> t;
    while(t--){
        bool pl = 1;
        int n, m;
        cin >> n >> m;
        int k,x;
        cin >> k;
        vector<int> good;
        for(int i=0;i<k;i++){
            cin >> x;
            good.push_back(x);
        }
        if(m==1){
            cout << 1<< "\n";
            continue;
        }
        vector<vector<vector<bool>>> dp(2, vector<vector<bool>>(n + 1));
        int cntt = 0;
        for (int i = 1; i <= n; i++)
        {
    
            dp[0][i].resize(1 << i);
            dp[1][i].resize(1 << i);
            if (i == 1)
            {
                for (int j = 0; j <= 1; j++)
                {
                    for (int k = 0; k <= 1; k++)
                    {
                        dp[j][i][k] = k;
                    }
                }
            }
            else
            {
                for (int msk = 0; msk < (1 << i); msk++)
                {
                    bool ans0 = 1;
                    bool ans1 = 0;
                    for (auto x :good)
                    {
                        if (x <= i)
                        {
                            cntt++;
                            int finmsk = removebit(msk, x - 1);
                            ans0 &= dp[1][i - 1][finmsk];
                            ans1 |= dp[0][i - 1][finmsk];
                        }
                        else
                        {
                            break;
                        }
                    }
                    dp[0][i][msk] = ans0;
                    dp[1][i][msk] = ans1;
                }
            }
        }
        mint finans = 0;
        for (int r = 0; r < (1<<n); r++)
        {   
            finans += 1+dp[pl][n][r];
            
        }
        cout << finans << endl;
    }
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
int removebit(int n, int bit)
{
    int msk = (1 << 22);
    int filtermask = msk - (1 << bit);
    return ((n >> 1) & filtermask) | (n & ((1 << bit) - 1));
}

const int maxn = 20;
const int maxm = 30;
 
ll binpow(ll a,ll b,ll m = MOD){
    ll res = 1;
    while (b){
        if (b&1) res = (res*a)%m;
        a = (a*a)%m;
        b>>=1;
    }
    return res;
}
int main()
{   int t;
    cin >> t;
    while(t--){
        bool pl = 1;
        int n, m;
        cin >> n >> m;
        int k,x;
        cin >> k;
        vector<int> good;
        for(int i=0;i<k;i++){
            cin >> x;
            good.push_back(x);
        }
        vector<vector<vector<bool>>> dp(2, vector<vector<bool>>(n + 1));
        vector<vector<vector<int>>> cnt(2, (n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1))));
        int cntt = 0;
        for (int i = 1; i <= n; i++)
        {
    
            dp[0][i].resize(1 << i);
            dp[1][i].resize(1 << i);
            if (i == 1)
            {
                for (int j = 0; j <= 1; j++)
                {
                    for (int k = 0; k <= 1; k++)
                    {
                        dp[j][i][k] = k;
                    }
                    cnt[j][1][1]++;
                }
            }
            else
            {
                for (int msk = 0; msk < (1 << i); msk++)
                {
                    bool ans0 = 1;
                    bool ans1 = 0;
                    for (auto x :good)
                    {
                        if (x <= i)
                        {
                            cntt++;
                            int finmsk = removebit(msk, x - 1);
                            ans0 &= dp[1][i - 1][finmsk];
                            ans1 |= dp[0][i - 1][finmsk];
                        }
                        else
                        {
                            break;
                        }
                    }
                    dp[0][i][msk] = ans0;
                    dp[1][i][msk] = ans1;
                    cnt[0][i][__popcount(msk)] += ans0;
                    cnt[1][i][__popcount(msk)] += ans1;
                }
            }
        }
        ll finans = 0;
        for (int r = 1; r <= n; r++)
        {   
            for(int k=1;k<=m;k++){
                finans += (((binpow(k-1,n-r)*binpow(m-k+1,r))%MOD) * (cnt[pl][n][r]))%MOD;
            }
        }
        cout << finans%MOD << endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<ll, ll> pl;
#define fo(i, a, b) for (ll i = a; i < b; i++)
#define pb push_back

ll gcd(ll a,ll b){
    if(a==0)return b;
    else return gcd(b%a,a);
}
vl a;
ll lc, s, n;
bool good(){
    bool v=1;
    if(n>23){
        fo(i,0,n){
            if(a[i]!=a[0]){
                v=0;
                break;
            }
        }
    }
    else{
        fo(i,2,n){
            fo(j,0,n){
                if((a[j]%i)!=(a[0]%i)){
                    v=0;
                    break;
                }
            }
        }
    }
    v&=(s%n==0);
    return v;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    ll T;
    cin >> T;
    while (T--) {
        cin >> n;
        a.clear();
        a.resize(n);
        s=0;
        fo(i,0,n){
            cin >> a[i];
            s+=a[i];
        }
        sort(a.begin(),a.end());
        lc=1;
        if(n>23){
            lc=1e10;
        }
        else{
            fo(i,2,n+1){
                lc=(lc*i)/gcd(lc,i);
            }
        }
        if(good()){
            cout << s<< "\n";
            continue;
        }
        a[0]--;
        s--;
        if(good()){
            cout << s<< "\n";
            continue;
        }
        cout << -1 << "\n";


    }
}