Abed is so motivated this year, his goal is qualifying for the 2019 ACM International Collegiate Programming Contest (ACM ICPC). Therefore, he always trains using Codeforces online judge. If you do not know Codeforces, the following rules can help you to understand how it works:

Each problem has a set of n tests numbered from 1 to n. The first k tests are called sample tests. These tests are visible in the problem statement and a user can see them all.
When Abed gets a wrong answer on test x (x ≤ n), he can see all the tests up to test number x. If Abed gets accepted, he can see all the tests.
Each test can be either small or big. Abed can see the entire test only if it is small. If the test is big, Abed can see it partially. All the sample tests are small.

For example, let us consider a problem contains 6 tests, in which the first two tests are the sample tests. If Abed got a wrong answer on test 4, a wrong answer on test 3, and a wrong answer on test 5, he can see all tests from 1 to 5. If test 3 is small and the tests from 4 to 6 are big, Abed can see the first three tests fully, but he cannot fully see the remaining tests.

Unfortunately, Abed usually gets a lot of wrong answers. A submission made by Abed is called stupid if he got a wrong answer on a small test that he can see it fully. You are given a list of submissions made be Abed, your task is to count how many stupid submission Abed has made. Can you?
Input

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains three integers n, m, and k (1 ≤ k ≤ n ≤ 10^4, 1 ≤ m ≤ 10^4), in which n is the number of tests in the problem, m is the number of submissions Abed has made, and k is the number of sample tests. Then a line follow contains n characters t1, …, tn, in which ti is ‘S’ if the ith test is small, and ‘B’ if it is big.

Then m lines follow, giving the list of submissions Abed has made, such that the ith line will either contain a single character ‘A’ if Abed got accepted on the ith submission, or contain a character ‘W’ and an integer x (1 ≤ x ≤ n) giving that Abed got a wrong answer on test case x.
Output

For each test case, print a single line containing the number of stupid submissions Abed has made.
Example
Input

2
5 4 2
S S B S B
W 3
W 4
W 4
A
4 3 2
S S B B
W 1
W 2
W 3

Output

1
2
n是测试点数，m是提交数，k是测试样例数（即前几个能看到）
如果测试样例错了或者S测试点错过又错，则愚蠢值+1

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e4+5;
int mp[maxn],vis[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,k,maxx;
        scanf("%d%d%d",&n,&m,&k);
        maxx=k;
        for(int i=0;i<=n;i++)
            mp[i]=0;
        getchar();
        for(int i=1;i<=n;i++)
        {
            char c;
            scanf("%c",&c);
            getchar();
            if(c=='S')
                mp[i]=1;
            else
                mp[i]=0;
        }
        int ans=0;
        for(int i=0;i<m;i++)
        {
            char c;
            scanf("%c",&c);
            getchar();
            if(c=='A')
            {
                maxx=n;
                continue;
            }
            else
            {
                int id;
                scanf("%d",&id);
                getchar();
                if(id<=maxx)
                    ans+=mp[id];
                maxx=max(maxx,id);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}