Problem: Polycarp has 26 tasks. Each task is designated by a capital letter of the Latin alphabet.

The teacher asked Polycarp to solve tasks in the following way: if Polycarp began to solve some task, then he must solve it to the end, without being distracted by another task. After switching to another task, Polycarp cannot return to the previous task.

Polycarp can only solve one task during the day. Every day he wrote down what task he solved. Now the teacher wants to know if Polycarp followed his advice.

For example, if Polycarp solved tasks in the following order: "DDBBCCCBBEZ", then the teacher will see that on the third day Polycarp began to solve the task 'B', then on the fifth day he got distracted and began to solve the task 'C', on the eighth day Polycarp returned to the task 'B'. Other examples of when the teacher is suspicious: "BAB", "AABBCCDDEEBZZ" and "AAAAZAAAAA".

If Polycarp solved the tasks as follows: "FFGZZZY", then the teacher cannot have any suspicions. Please note that Polycarp is not obligated to solve all tasks. Other examples of when the teacher doesn't have any suspicious: "BA", "AFFFCC" and "YYYYY".

Help Polycarp find out if his teacher might be suspicious.

Input

The first line contains an integer t (1 ≤ t ≤ 1000). Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 50) — the number of days during which Polycarp solved tasks.

The second line contains a string of length n, consisting of uppercase Latin letters, which is the order in which Polycarp solved the tasks.

Output

For each test case output: 

  * "YES", if the teacher cannot be suspicious; 
  * "NO", otherwise. 



You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).

Example

Input


5
3
ABA
11
DDBBCCCBBEZ
7
FFGZZZY
1
Z
2
AB


Output


NO
NO
YES
YES
YES

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#include <vector>
using namespace std;


#define f(i,n)          for(int i=0;i<n;i++)
#define FOR(i,a,b)      for(int i=a;i<b;i++)
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x  //works with float
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define all(x)          x.begin(),x.end()
#define rt              return
#define br              break
#define ct              continue
#define elif            else if
#define arrin(a,n)      for(int i=0;i<n;i++)cin>>a[i]
#define arrout(a,n)     for(int i=0;i<n;i++)cout<<a[i]<<" "
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

int log_a_to_base_b(int a, int b)
{
    return log(a) / log(b);
}

void c_p_c()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
}

string subsequence(string s, int binary, int len)
{
    string sub = "";
    for (int j = 0; j < len; j++)

        // check if jth bit in binary is 1
        if (binary & (1 << j))

            // if jth bit is 1, include it
            // in subsequence
            sub += s[j];

    return sub;
}

// function to print all subsequences
vector<string> possibleSubsequences(string s) {

    vector<string> vs;

    // map to store subsequence
    // lexicographically by length
    map<int, set<string> > sorted_subsequence;

    int len = s.size();

    // Total number of non-empty subsequence
    // in string is 2^len-1
    int limit = pow(2, len);

    // i=0, corresponds to empty subsequence
    for (int i = 1; i <= limit - 1; i++) {

        // subsequence for binary pattern i
        string sub = subsequence(s, i, len);

        // storing sub in map
        sorted_subsequence[sub.length()].insert(sub);
    }

    for (auto it : sorted_subsequence) {

        // it.first is length of Subsequence
        // it.second is set<string>
        cout << "Subsequences of length = "
             << it.first << " are:" << endl;

        for (auto ii : it.second) {

            // ii is iterator of type set<string>
            cout << ii << " ";
            vs.pb(ii);
        }

        cout << endl;
    }
    return vs;
}


string DecimalToBinaryString(int a)
{
    string binary = "";
    int mask = 1;
    for (int i = 0; i < 31; i++)
    {
        if ((mask & a) >= 1)
            binary = "1" + binary;
        else
            binary = "0" + binary;
        mask <<= 1;
    }
    // cout<<binary<<endl;
    return binary;
}



int32_t main()
{


    w(t) {
        int l;
        cin >> l;
        string s;
        cin >> s;
        string s2 = s;
        int a[26] = {0};
        bool b1 = false;

        f(i, l) {
            int d = s.at(i);
            d -= 65;
            if (a[d] == 0) {
                a[d] = 1;
            }
            else if (a[d] == 1 and s.at(i) == s.at(i - 1) and i != 0) {
                continue;
            }
            else {
                b1 = true;
            }

        }

        if (b1) {
            cout << "NO" << endl;
        }
        else
            cout << "YES" << endl;
        // sort(s2.begin(), s.end());
        // reverse(s2.begin(), s2.end());

        // bool b1 = false, b2 = false;

        // if (is_sorted(s.begin(), s.end())) {
        //     b1 = true;
        // }
        // if (s2 == s) {
        //     b2 = true;
        // }
        // if (b2 or b1) {
        //     cout << "YES" << endl;
        // }
        // else
        //     cout << "NO" << endl;





    }






}