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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Solve {

	static int mod = 1000000000 + 7;
	static long fact[] = new long[2 * 100000 + 3];

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner();
		PrintWriter pw = new PrintWriter(System.out);
		int t = sc.nextInt();
		while (t-- > 0) {
			int n = sc.nextInt();
			String str = sc.next();

			boolean valid = true;
			int a[] = new int[1000];
			a[str.charAt(0)] = 0;
			for (int i = 1; i < n; i++) {
				if (a[str.charAt(i)] == 1)
					valid = false;
				if (str.charAt(i) != str.charAt(i - 1)) {
					a[str.charAt(i - 1)] = 1;
				}

			}
			System.out.println(valid ? "YES" : "NO");

		}

		pw.flush();

	}

	static public boolean isInterleave(String s1, String s2, String s3) {
		int n = s1.length();
		int m = s2.length();
		int k = s3.length();

		boolean dp[][][] = new boolean[n + 2][m + 2][k + 2];
		dp[0][0][0] = true;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				dp[i][j][0] = true;

			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				for (int l = 1; l <= k; l++) {
					char c1 = s1.charAt(i - 1);
					char c2 = s2.charAt(j - 1);

					char c3 = s3.charAt(l - 1);

					if (c1 == c3) {
						dp[i][j][l] = dp[i][j][l] || dp[i - 1][j][l - 1];

					}

					if (c2 == c3) {
						dp[i][j][l] = dp[i][j][l] || dp[i][j - 1][l - 1];

					}
				}
			}
		}
		return dp[n][m][k];

	}

	static long gcd(long a, long b) {
		if (a == 0)
			return b;
		if (b == 0)
			return a;

		return gcd(b, a % b);

	}

	static long nC2(long n) {
		return n * (n - 1) / 2;
	}

	static long nCrModp(int n, int r, int p) {
		if (r > n - r)
			r = n - r;

		// The array C is going to store last
		// row of pascal triangle at the end.
		// And last entry of last row is nCr
		int C[] = new int[r + 1];

		C[0] = 1; // Top row of Pascal Triangle

		// One by constructs remaining rows of Pascal
		// Triangle from top to bottom
		for (int i = 1; i <= n; i++) {

			// Fill entries of current row using previous
			// row values
			for (int j = Math.min(i, r); j > 0; j--)

				// nCj = (n-1)Cj + (n-1)C(j-1);
				C[j] = (C[j] + C[j - 1]) % p;
		}
		return C[r];
	}

	static void sort(int[] a) {
		ArrayList<Integer> l = new ArrayList<>();
		for (int i : a)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < a.length; i++)
			a[i] = l.get(i);
	}

	public int subarrayBitwiseORs(int[] arr) {
		int n = arr.length;
		HashSet<Integer> set1 = new HashSet<Integer>();
		HashSet<Integer> ans = new HashSet<Integer>();

		set1.add(0);
		for (int i = 0; i < n; i++) {
			HashSet<Integer> cur = new HashSet<Integer>();
			set1.add(0);

			for (Integer j : set1)
				cur.add(arr[i] | j);

			set1 = (cur);
			ans.addAll(set1);

		}
		return ans.size();

	}

}

class Pair implements Comparable<Pair> {
	int tower;
	int value = 0;

	Pair(int x, int y) {
		tower = x;
		value = y;
	}

	public int compareTo(Pair o) {
		return this.value - o.value;
	}

}

class Scanner {
	BufferedReader br;
	StringTokenizer st;

	Scanner() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	String next() throws IOException {
		while (st == null || !st.hasMoreElements())
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}

	int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(next());
	}

	long nextLong() throws NumberFormatException, IOException {
		return Long.parseLong(next());
	}

	double nextDouble() throws NumberFormatException, IOException {
		return Double.parseDouble(next());
	}
}

//creating a hash table
//Hashtable<Integer, String> h = new Hashtable<Integer, String>();
//
//Hashtable<Integer, String> h1 = new Hashtable<Integer, String>();
//
//h.put(3, "Geeks");
//h.put(2, "forGeeks");
//h.put(1, "isBest");
//System.out.println(h.get(1));
//if (h.containsKey(1)) {
//	System.out.println(1111111);
//}
//if (h.containsValue("isBest")) {
//	System.out.println(1111111);
//}
//
//// create a clone or shallow copy of hash table h
//h1 = (Hashtable<Integer, String>) h.clone();
//
//// checking clone h1
////System.out.println("values in clone: " + h1);
//
//// clear hash table h
//h.clear();

//Creating object of the 
// class linked list 
//LinkedList<String> ll 
//    = new LinkedList<String>(); 
//
//// Adding elements to the linked list 
//ll.add("A"); 
//ll.add("B"); 
//ll.addLast("C"); 
//ll.addFirst("D"); 
//ll.add(2, "E"); 
//
//System.out.println(ll); 
//
//ll.remove("B"); 
//ll.remove(3); 
//ll.removeFirst(); 
//ll.removeLast(); 
//
//System.out.println(ll); 

//Set<Integer> set = new HashSet<Integer>();
//try {
//   for(int i = 0; i < 5; i++) {
//      set.add(count[i]);
//   }
//   System.out.println(set);
//
//   TreeSet sortedSet = new TreeSet<Integer>(set);
//   System.out.println("The sorted list is:");
//   System.out.println(sortedSet);
//
//   System.out.println("The First element of the set is: "+ (Integer)sortedSet.first());
//   System.out.println("The last element of the set is: "+ (Integer)sortedSet.last());
//}
//catch(Exception e) {}