#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define size(n) ( int( n.size() ) )
#define sqr(n) ( (n) * (n) )
#define fi first
#define se second

typedef long long ll;

using namespace std;

ll ans = 0;
const int N = 1e6 + 5, base = 41, MX = 1e7 + 5;
int a[N], ls[MX], rs[MX], mod[2], pwr[N][2], cntVers = 0, root[MX], t[MX][2], sz = 1, cntv = 0;
set < pair < int, int > > ss;

void addVers( int idx, int val ){
    int tl = 1, tr = sz;
    cntVers++;
    int v = root[cntVers-1];
    vector < pair < int, int > > path;
    while( tl != tr ){
        int tm = ( tl + tr ) >> 1;
        if ( idx <= tm ){
            path.pb( mp( v, 0 ) );
            v = ls[v];
            tr = tm;
        }
        else{
            path.pb( mp( v, 1 ) );
            v = rs[v];
            tl = tm + 1;
        }
    }
    cntv++;
    t[cntv][0] = val;
    t[cntv][1] = val;
    for ( int i = size(path) - 1; i >= 0; i-- ){
        int par = path[i].fi;
        int tp = path[i].se;
        cntv++;
        if ( tp == 0 ){
            ls[cntv] = cntv-1;
            rs[cntv] = rs[par];
            tr = 2 * tr - tl + 1;
        }
        else{
            ls[cntv] = ls[par];
            rs[cntv] = cntv-1;
            tl = 2 * tl - tr - 1;
        }
        int len = ( tr - tl + 1 ) >> 1;
        for ( int j = 0; j <= 1; j++ ){
            t[cntv][j] = ( t[ ls[cntv] ][j] + ( t[ rs[cntv] ][j] * 1ll * pwr[len][j] ) ) % mod[j];
        }
    }
    root[cntVers] = cntv;
}

struct cmp{
    bool operator() (const int &x, const int &y){
        int v = root[x];
        int u = root[y];
        //cout << x << " " << y << endl;
        int tl = 1, tr = sz;
        while( tl != tr ){
            int tm = ( tl + tr )  >> 1;
            if ( ( t[ ls[v] ][0] == t[ ls[u] ][0] ) && ( t[ ls[v] ][1] == t[ ls[u] ][1] ) ){
                v = rs[v];
                u = rs[u];
                tl = tm + 1;
            }
            else{
                v = ls[v];
                u = ls[u];
                tr = tm;
            }
        }
        return ( t[v][0] < t[u][0] );
    }
};

set < int, cmp > s;
set < int, cmp > :: iterator it, itL, itR;

void build( int v, int tl, int tr ){
    t[v][0] = 0;
    t[v][1] = 0;
    if ( tl == tr ){
        return;
    }
    int tm = ( tl + tr ) >> 1;
    ++cntv;
    ls[v] = cntv;
    ++cntv;
    rs[v] = cntv;
    build( ls[v], tl, tm );
    build( rs[v], tm + 1, tr );
}

int getLcp( int x, int y ){
    int res = 0;
    int v = root[x], u = root[y];
    int tl = 1, tr = sz;
    while( tl != tr ){
        int len = ( tr - tl + 1 ) >> 1;
        int tm = ( tl + tr ) >> 1;
        if ( ( t[ ls[v] ][0] == t[ ls[u] ][0] ) && ( ( t[ ls[v] ][1] == t[ ls[u] ][1] ) ) ){
            res += len;
            v = rs[v];
            u = rs[u];
            tl = tm + 1;
        }
        else{
            v = ls[v];
            u = ls[u];
            tr = tm;
        }
    }
    return res;
}

int main(){
//    freopen("input.txt","r",stdin);
//    freopen("outputSol.txt","w",stdout);
    //freopen("output.txt","w",stdout);
    mod[0] = 1e9 + 7;
    mod[1] = 1e9 + 9;
    for ( int j = 0; j <= 1; j++ ){
        pwr[0][j] = 1;
        for ( int i = 1; i < N; i++ ){
            pwr[i][j] = ( pwr[i-1][j] * 1ll * base ) % mod[j];
        }
    }
    int cases;
    scanf("%d",&cases);
    for ( int pCases = 1; pCases <= cases; pCases++ ){
        s.clear();
        ss.clear();
        cntv = 0;
        cntVers = 0;
        int n, q;
        sz = 1;
        scanf("%d %d\n",&n,&q);
        while( sz < n ){
            sz *= 2;
        }
        cntv++;
        root[0] = cntv;
        build( 1, 1, sz );
        char ch;
        ans = 1;
        for ( int i = 1; i <= q; i++ ){
            scanf("%c",&ch);
            if ( ch == '?' ){
                printf("%lld\n",ans);
            }
            else{
                int c;
                scanf("%d",&c);
                while( ( c <= n - 1 ) && ( a[c] == 1 ) ){
                    addVers( n - c, 0 );
                    a[c] = 0;
                    c++;
                }
                if ( c <= n - 1 ){
                    a[c] = 1;
                    addVers( n - c, 1 );
                }
                if( ss.find( mp( t[cntv][0], t[cntv][1] ) ) == ss.end() ){
                    ss.insert( mp( t[cntv][0], t[cntv][1] ) );
                    s.insert( cntVers );
                    it = s.find(cntVers);
                    int mx = 0;
                    if ( it != s.begin() ){
                        itL = it;
                        itL--;
                        mx = max( mx, getLcp( (*it), (*itL) ) );
                    }
                    itR = it;
                    itR++;
                    if ( itR != s.end() ){
                        mx = max( mx, getLcp( (*it), (*itR) ) );
                    }
                    ans += n - mx;
                }
            }
            scanf("\n");
        }
        for ( int i = 0; i <= n - 1; i++ ){
            a[i] = 0;
        }
    }
    return 0;
}