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.*;
import java.math.*;
import java.util.*;
public class Q1 {
	static int INF = (int)(1e9);
	static long mod = (long)(1e9)+7;
	static long mod2 = 998244353;
	static long[] segtree;
	static char[] curans;
	static long ans;	
	static String S;
	static ArrayList<Integer>[] graph;
	static boolean[] vis;
	static int[] a;
	static int N;
	static long K;
	static long[] fact;
	static ArrayList<Long> pos;
	static ArrayList<Long> neg;
	static long[] max;
	static int[] dp;
	public static void main(String[] args) {  //Cash out
		/**/
		FastScanner I = new FastScanner(); //Input
		OutPut O = new OutPut(); //Output
		int T = I.nextInt();
		StringBuilder ret = new StringBuilder();
		while (T-- > 0) {
			int N = I.nextInt();
			String S = I.next();
			
			boolean[] vis = new boolean[200];
			boolean bad = false;
			for (int i = 0; i < N; i++) {
				char c = S.charAt(i);
				
				if (vis[c] && S.charAt(i - 1) != c) {
					bad = true;
				}
				
				vis[c] = true;
			}
			
			ret.append(bad? "NO\n" : "YES\n");
		}
		O.pln(ret);
	}
	public static double[][] matrix_exp(double[][] a, long exp, long mod) {
		int R = a.length;
		int C = a[0].length;
		double[][] ans = new double[R][C];
		
		boolean mult_yet = false;
		
		while (exp > 0) {
			if (exp % 2 == 1) {
				if (!mult_yet) {
					mult_yet = true;
					for (int i = 0; i < R; i++) {
						for (int j = 0; j < C; j++) {
							ans[i][j] = a[i][j]; 
						}
					}
				}else {
					double[][] new_ans = mult(ans, a, mod);
					for (int i = 0; i < R; i++) {
						for (int j = 0; j < C; j++) {
							ans[i][j] = new_ans[i][j]; 
						}
					}
				}
			}
			
			double[][] new_a = mult(a, a, mod); // a = a^2 (binary exponentiation on matrices)
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					a[i][j] = new_a[i][j]; 
				}
			}
			exp /= 2;
		}
		
		return ans;
	}
	public static double[][] mult(double[][] a, double[][] b, long mod) {
		int r1 = a.length;
		int c1 = a[0].length;
		int r2 = b.length;
		int c2 = b[0].length;
		//Requires: c1 = r2
		
		double[][] ans = new double[r1][c2];
		for (int r = 0; r < r1; r++) {
			for (int c = 0; c < c2; c++) {
				//Dot product of (a[r])^T and b[c] (as vectors in R^n (n = c1 = r2))
				double[] col_vector = new double[r2];
				double[] row_vector = new double[c1];
				
				for (int i = 0; i < r2; i++) {
					col_vector[i] = b[i][c];
				}
				for (int i = 0; i < c1; i++) {
					row_vector[i] = a[r][i]; 
				}
				
				ans[r][c] = dot_product(row_vector, col_vector, mod);
			}
		}
		return ans;
	}
	
	public static double dot_product(double[] a, double[] b, long mod) {
		double ans = 0;
		int N = a.length; //Requires: a and b are both vectors in R^n
		for (int i = 0; i < N; i++) {
			ans += a[i] * b[i];
		}
		return ans;
	}
	public static double max(double a, double b) {return Math.max(a, b);}
	public static double min(double a, double b) {return Math.min(a, b);}
	public static long min(long a, long b) {return Math.min(a,b);}
	public static long max(long a, long b) {return Math.max(a,b);}
	public static int min(int a, int b) {return Math.min(a,b);}
	public static int max(int a, int b) {return Math.max(a,b);}
	public static long abs(long x) {return Math.abs(x);}
	public static long abs(int x) {return Math.abs(x);}
	public static long ceil(long num, long den) {long ans = num/den; if (num%den!=0) 
	ans++; return ans;}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return max(a,b);
		return GCD(min(a,b),max(a,b)%min(a,b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	public static int pop(long x) { //Returns number of bits within a number
		int cnt = 0;
		while (x>0) {
			if (x%2==1) cnt++;
			x/=2;
		}
		return cnt;
	}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());};
		double nextDouble() {return Double.parseDouble(next());}
	}
	static class OutPut{
		PrintWriter w = new PrintWriter(System.out);
		void pln(double x) {w.println(x);w.flush();}
		void pln(boolean x) {w.println(x);w.flush();}
		void pln(int x) {w.println(x);w.flush();}
		void pln(long x) {w.println(x);w.flush();}
		void pln(String x) {w.println(x);w.flush();}
		void pln(char x) {w.println(x);w.flush();}
		void pln(StringBuilder x) {w.println(x);w.flush();}
		void pln(BigInteger x) {w.println(x);w.flush();}
		void p(int x) {w.print(x);w.flush();}
		void p(long x) {w.print(x);w.flush();}
		void p(String x) {w.print(x);w.flush();}
		void p(char x) {w.print(x);w.flush();}
		void p(StringBuilder x) {w.print(x);w.flush();}
		void p(BigInteger x) {w.print(x);w.flush();}
		void p(double x) {w.print(x);w.flush();}
		void p(boolean x) {w.print(x);w.flush();}
	}
}