You are given a string s consisting of lowercase Latin characters. In an operation, you can take a character and replace all occurrences of this character with 0 or replace all occurrences of this character with 1.

Is it possible to perform some number of moves so that the resulting string is an alternating binary string??

For example, consider the string abacaba. You can perform the following moves:

Replace a with 0. Now the string is 0b0c0b0.

Replace b with 1. Now the string is 010c010.

Replace c with 1. Now the string is 0101010. This is an alternating binary string.?

An alternating binary string is a string of 0s and 1s such that no two adjacent bits are equal. For example, 01010101, 101, 1 are lternating binary strings, but 0110, 0a0a0, 10100 are not.

Input

The input consists of multiple test cases. The first line contains an integer t (1≤t≤100) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer n (1≤n≤2000) -the length of the string s.

The second line of each test case contains a string consisting of n

?lowercase Latin characters — the string s.

Output

For each test case, output "YES" (without quotes) if you can make the string into an alternating binary string, and "NO" (without quotes) otherwise.

You can output the answer in any case (for example, the strings “”yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

----------------------------------

給定一個(gè)由小寫拉丁字符組成的字符串 s。 在運(yùn)算中，您可以獲取一個(gè)字符，并將所有出現(xiàn)的該字符替換為 0，或者將所有出現(xiàn)的該字符替換為 1。

是否可以執(zhí)行一定次數(shù)的移動(dòng)以使結(jié)果字符串成為交替的二進(jìn)制字符串?？

例如，考慮字符串 abacaba。 您可以執(zhí)行以下操作：

將 a 替換為 0。現(xiàn)在字符串為 0b0c0b0。

將 b 替換為 1?，F(xiàn)在字符串為 010c010。

將 c 替換為 1?，F(xiàn)在字符串是 0101010。這是一個(gè)交替的二進(jìn)制字符串。?

交替的二進(jìn)制字符串是由 0 和 1 組成的字符串，任何兩個(gè)相鄰位都不相等。 例如，01010101、101、1 是交替二進(jìn)制字符串，但 0110、0a0a0、10100 不是。

輸入

輸入由多個(gè)測試用例組成。 第一行包含一個(gè)整數(shù) t (1≤t≤100) — 測試用例的數(shù)量。 測試用例的描述如下。

每個(gè)測試用例的第一行包含一個(gè)整數(shù)n（1≤n≤2000）-字符串s的長度。

每個(gè)測試用例的第二行包含一個(gè)由n組成的字符串

? 小寫拉丁字符 — 字符串 s。

輸出

對于每個(gè)測試用例，如果可以將字符串變成交替的二進(jìn)制字符串，則輸出“YES”（不帶引號(hào)），否則輸出“NO”（不帶引號(hào)）。

您可以在任何情況下輸出答案（例如，字符串“”yEs”、“yes”、“Yes”和“YES”將被識(shí)別為肯定答案）。

------------------

用hashmap保存每個(gè)字母對應(yīng)的值，如果遇到?jīng)]有的，根據(jù)flag是去判斷，如果出錯(cuò)了，就返回false，沒問題就輸出yes

下面是代碼：