{"raw_statement":[{"iden":"statement","content":"Abed is so motivated this year, his goal is qualifying for the 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: \n\nFor 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.\n\nUnfortunately, 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?\n\nThe first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.\n\nThe first line of each test case contains three integers n, m, and k (1 ≤ k ≤ n ≤ 104, 1 ≤ m ≤ 104), 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.\n\nThen 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.\n\nFor each test case, print a single line containing the number of stupid submissions Abed has made.\n\n"},{"iden":"input","content":"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 ≤ 104, 1 ≤ m ≤ 104), 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."},{"iden":"output","content":"For each test case, print a single line containing the number of stupid submissions Abed has made."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ j \\in \\{1, \\dots, T\\} $:  \n- Let $ n_j \\in \\mathbb{Z} $ be the total number of test cases.  \n- Let $ m_j \\in \\mathbb{Z} $ be the number of submissions.  \n- Let $ k_j \\in \\mathbb{Z} $ be the number of sample tests (initially visible).  \n- Let $ T_j = (t_1, t_2, \\dots, t_{n_j}) \\in \\{S, B\\}^{n_j} $ be the type sequence, where $ t_i = S $ if test $ i $ is small, $ B $ if big.  \n- Let $ S_j = (s_1, s_2, \\dots, s_{m_j}) $ be the sequence of submissions, where each $ s_i $ is either:  \n  - $ A $ (accepted), or  \n  - $ (W, x_i) $ with $ x_i \\in \\{1, \\dots, n_j\\} $ (wrong answer on test $ x_i $).  \n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. For each $ j \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le k_j \\le n_j \\le 10^4 $  \n   - $ 1 \\le m_j \\le 10^4 $  \n   - $ t_i \\in \\{S, B\\} $ for all $ i \\in \\{1, \\dots, n_j\\} $  \n   - For each wrong submission: $ 1 \\le x_i \\le n_j $  \n\n**Objective**  \nFor each test case $ j $, count the number of **stupid submissions**, defined as:  \nA submission $ s_i $ is *stupid* if:  \n- $ s_i = (W, x_i) $ (i.e., wrong answer on test $ x_i $), and  \n- $ t_{x_i} = S $ (the failed test is small), and  \n- $ x_i \\le \\max\\{x_{i'} \\mid s_{i'} = (W, x_{i'}) \\text{ and } i' < i\\} \\cup \\{k_j\\} $ (i.e., test $ x_i $ is fully visible — meaning it is among the first $ \\ell $ tests, where $ \\ell $ is the maximum test index among all previously failed tests or the sample tests).  \n\nEquivalently, for submission $ i $:  \nLet $ \\ell_i = \\max( k_j, \\max\\{ x_{i'} \\mid i' < i \\text{ and } s_{i'} = (W, x_{i'}) \\} ) $, with $ \\ell_i = k_j $ if no prior wrong submission.  \nThen $ s_i $ is stupid iff $ s_i = (W, x_i) $, $ t_{x_i} = S $, and $ x_i \\le \\ell_i $.  \n\n**Output**  \nFor each test case $ j $, output the count of stupid submissions.","simple_statement":"Count how many of Abed’s submissions are \"stupid\": a submission is stupid if he got WA on a small test that he can see fully. He can see all tests up to the first WA (including sample tests). Sample tests are the first k tests. A test is \"small\" if marked 'S', \"big\" if 'B'.","has_page_source":false}