{"raw_statement":[{"iden":"problem statement","content":"You have an $N \\times N$ grid board. You want to color all cells in $3$ colors so that no two adjacent (edge-sharing) cells have the same color.\nYou have already painted the border of the board. Determine if you can color the rest of the board properly.\nMore precisely, you are given a string $S$ of length $4N-4$ consisting of characters `1`, `2`, and `3`. The string denotes the colors of the cells on the border, starting from the cell $(1, 1)$, in clockwise order. Strictly speaking, the $i$\\-th character of $S$ denotes the color of the cell:\n\n*   $(1, i)$ for $1 \\le i \\le N-1$\n*   $(i - (N-1), N)$ for $N \\le i \\le 2N-2$\n*   $(N, 3N - 1 - i)$ for $2N-1 \\le i \\le 3N-3$\n*   $(4N-2 - i, 1)$ for $3N-2 \\le i \\le 4N-4$.\n\nHere, $(r,c)$ denotes the cell in the $r$\\-th row and the $c$\\-th column.\nIt is guaranteed that no two adjacent cells on the border have the same color.\nSolve $T$ test cases for each input file."},{"iden":"constraints","content":"*   $1 \\le T \\le 5 \\cdot 10^4$\n*   $3 \\le N \\le 2 \\cdot 10^5$\n*   $S$ is a string of length $4N-4$ consisting of characters `1`, `2`, and `3`.\n*   $S_i \\neq S_{i+1}$ for $1 \\le i \\le 4N-5$, and $S_{4N-4} \\neq S_1$.\n*   The sum of $N$ in one input file doesn't exceed $2\\cdot 10^5$.\n*   All numbers in the input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach case is in the following format:\n\n$N$\n$S$"},{"iden":"sample input 1","content":"4\n3\n12312312\n4\n121212121212\n7\n321312312312121212121321\n7\n321312312312121312121321"},{"iden":"sample output 1","content":"NO\nYES\nNO\nYES\n\nIt can be shown that there is no way to properly color the rest of the board in the first and the third test cases. The proper colorings for the second and fourth test cases are shown below.\n![image](https://img.atcoder.jp/agc059/1ada4c7ac4b8e04277788b67a8d2a71c.png)"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}