{"problem":{"name":"Right Side Character","description":{"content":"For a string $T=T_1T_2\\dots T_n$ of length $n\\ (2\\leq n)$ consisting of `A` and `B`, we define a string $f(T)$ of length $n-1$ as follows. *   Let $a_1 < a_2 < \\dots < a_{m}$ be the indices $i\\ (1\\le","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc062_a"},"statements":[{"statement_type":"Markdown","content":"For a string $T=T_1T_2\\dots T_n$ of length $n\\ (2\\leq n)$ consisting of `A` and `B`, we define a string $f(T)$ of length $n-1$ as follows.\n\n*   Let $a_1 < a_2 < \\dots < a_{m}$ be the indices $i\\ (1\\leq i \\leq n-1)$ such that $T_i={}$`A`, and $b_1 < b_2 < \\dots < b_k$ be the indices $i\\ (1\\leq i \\leq n-1)$ such that $T_i={}$`B`. Then, let $f(T)=T_{a_1+1}T_{a_2+1}\\dots T_{a_m+1}T_{b_1+1}T_{b_2+1}\\dots T_{b_k+1}$.\n\nFor example, for the string $T={}$`ABBABA`, the indices $i\\ (1\\leq i \\leq 5)$ with $T_i={}$`A` are $i=1,4$, and the indices $i\\ (1\\leq i \\leq 5)$ with $T_i={}$`B` are $i=2,3,5$, so $f(T)$ is $T_{1+1}T_{4+1}T_{2+1}T_{3+1}T_{5+1}={}$`BBBAA`.\nYou are given a string $S$ of length $N$ consisting of `A` and `B`.\nFind $S$ after replacing $S$ with $f(S)$ $(N-1)$ times.\nYou have $T$ test cases to solve.\n\n## Constraints\n\n*   $1 \\leq T \\leq 10^5$\n*   $2 \\leq N \\leq 3 \\times 10^5$\n*   $S$ is a string of length $N$ consisting of `A` and `B`.\n*   All numbers in the input are integers.\n*   The sum of $N$ over the test cases in a single input file is at most $3 \\times 10^5$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is given in the following format:\n\n$N$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc062_a","tags":[],"sample_group":[["3\n2\nAB\n3\nAAA\n4\nABAB","B\nA\nA\n\nIn the first test case, $S$ changes as `AB`${}\\rightarrow {}$`B`.\nIn the second test case, $S$ changes as `AAA`${} \\rightarrow {}$`AA`${} \\rightarrow {}$`A`.\nIn the third test case, $S$ changes as `ABAB`${}\\rightarrow {}$`BBA`${} \\rightarrow {}$`BA`${} \\rightarrow {}$`A`."]],"created_at":"2026-03-03 11:01:14"}}