Broken Keyboard
Contest: 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 800
Tags: greedy

Recently, Mishka started noticing that his keyboard malfunctions — maybe it's because he was playing rhythm games too much. Empirically, Mishka has found out that every other time he presses a key, it is registered as if the key was pressed twice. For example, if Mishka types text, the first time he presses a key, exactly one letter is printed; the second time he presses a key, two same letters are printed; the third time he presses a key, one letter is printed; the fourth time he presses a key, two same letters are printed, and so on. Note that the number of times a key was pressed is counted for the whole keyboard, not for each key separately. For example, if Mishka tries to type the word osu, it will be printed on the screen as ossu.

You are given a word consisting of $$$n$$$ lowercase Latin letters. You have to determine if it can be printed on Mishka's keyboard or not. You may assume that Mishka cannot delete letters from the word, and every time he presses a key, the new letter (or letters) is appended to the end of the word.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the word.

The second line of the test case contains a string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters — the word that should be checked.

Output format:
For each test case, print YES if the word $$$s$$$ can be printed on Mishka's keyboard, and NO otherwise.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
In the first test case, Mishka can type the word as follows: press o (one letter o appears at the end of the word), then presses s (two letters s appear at the end of the word), and, finally, press u (one letter appears at the end of the word, making the resulting word ossu).

In the second test case, Mishka can try typing the word as follows: press a (one letter a appears at the end of the word). But if he tries to press a one more time, two letters a will appear at the end of the word, so it is impossible to print the word using his keyboard.

In the fourth test case, Mishka has to start by pressing q. Then, if he presses w, two copies of w will appear at the end of the word, but the third letter should be e instead of w, so the answer is NO.

Example input:
4
4
ossu
2
aa
6
addonn
3
qwe

Example output:
YES
NO
YES
NO

Editorial:
There are many ways to solve this problem. Basically, we need to check two conditions.
The first one is the condition on the number of characters: $$$n \bmod 3 \ne 2$$$, since after the first key press, we get the remainder $$$1$$$ modulo $$$3$$$, after the second key press, we get the remainder $$$0$$$ modulo $$$3$$$, then $$$1$$$ again, then $$$0$$$ — and so on, and we cannot get the remainder $$$2$$$.
Then we need to check that, in each pair of characters which appeared from the same key press, these characters are the same — that is, $$$s_2 = s_3$$$, $$$s_5 = s_6$$$, $$$s_8 = s_9$$$, and so on.