{"problem":{"name":"All the Same","description":{"content":"You are given a string $S$ of length $N$ consisting of the characters `A` and `B`. For a string $X$ of length $N$ consisting of the characters `1`, `2`, and `3`, the **score** is determined by the fol","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc179_f"},"statements":[{"statement_type":"Markdown","content":"You are given a string $S$ of length $N$ consisting of the characters `A` and `B`.\nFor a string $X$ of length $N$ consisting of the characters `1`, `2`, and `3`, the **score** is determined by the following procedure:\n\n> First, initialize the variables $h_1, h_2, h_3, P$ to $0$.\n> Then, for $i = 1, 2, \\dots, N$ in this order, perform the following operations:\n> \n> *   If the $i$\\-th character of $S$ is `A`, perform operation A; if it is `B`, perform operation B. Let $d$ be the number represented by the $i$\\-th character of $X$.\n>     *   **Operation A**: Add $2$ to $h_d$.\n>         \n>     *   **Operation B**: If $d = 2$ or $h_d \\neq h_2$, set $P$ to $-10^{100}$. Otherwise, add $1$ to both $h_d$ and $h_2$.\n>         \n> *   If $h_1 = h_2 = h_3$, add $1$ to $P$.\n>     \n> \n> The final value of $P$ is the score.\n\nPrint one string $X$ that maximizes the score.\nYou have $T$ test cases to solve.\n\n## Constraints\n\n*   $1 \\leq T \\leq 10^5$\n*   $1 \\leq N \\leq 10^6$\n*   $S$ is a string of length $N$ consisting of `A` and `B`.\n*   $T$ and $N$ are integers.\n*   The sum of $N$ across all test cases is at most $10^6$.\n\n## Input\n\nThe input is given from Standard Input in the following format. Here, $\\mathrm{test}_i$ denotes the $i$\\-th test case.\n\n$T$\n$\\mathrm{test}_1$\n$\\mathrm{test}_2$\n$\\vdots$\n$\\mathrm{test}_T$\n\nEach test case is given in the following format:\n\n$N$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc179_f","tags":[],"sample_group":[["5\n4\nABBA\n5\nAAAAA\n6\nBBBBBB\n7\nABABABA\n20\nAAABBBBBBBBAAABBBABA","1333\n12321\n333333\n1313212\n33311111133121111311\n\nLet us describe the changes in $(h_1, h_2, h_3, P)$ as we proceed with $i = 1, 2, \\dots, N$.\n\n*   For the first test case, $(0,0,0,0) \\rightarrow (2,0,0,0) \\rightarrow (2,1,1,0) \\rightarrow (2,2,2,1) \\rightarrow (2,2,4,1)$. The maximum score is $1$.\n*   For the second test case, $(0,0,0,0) \\rightarrow (2,0,0,0) \\rightarrow (2,2,0,0) \\rightarrow (2,2,2,1) \\rightarrow (2,4,2,1) \\rightarrow (4,4,2,1)$. The maximum score is $1$.\n\nFor the third, fourth, and fifth test cases, the maximum scores are $0$, $0$, and $2$, respectively. There may be multiple strings $X$ that maximize the score, but you only need to print one of them."]],"created_at":"2026-03-03 11:01:14"}}