time limit per test

2 seconds

memory limit per test

256 megabytes

Monocarp is working on his new site, and the current challenge is to make the users pick strong passwords.

Monocarp decided that strong passwords should satisfy the following conditions:

• password should consist only of lowercase Latin letters and digits;
• there should be no digit that comes after a letter (so, after each letter, there is either another letter or the string ends);
• all digits should be sorted in the non-decreasing order;
• all letters should be sorted in the non-decreasing order.

Note that it's allowed for the password to have only letters or only digits.

Monocarp managed to implement the first condition, but he struggles with the remaining ones. Can you help him to verify the passwords?

Input

The first line contains a single integer tt (1≤t≤10001≤t≤1000) — the number of testcases.

The first line of each testcase contains a single integer nn (1≤n≤201≤n≤20) — the length of the password.

The second line contains a string, consisting of exactly nn characters. Each character is either a lowercase Latin letter or a digit.

Output

For each testcase, print "YES" if the given password is strong and "NO" otherwise.

Example

Input

Copy

5

4

12ac

5

123wa

9

allllmost

5

ac123

6

011679

Output

Copy

YES
NO
YES
NO
YES

Note

In the second testcase, the letters are not sorted in the non-decreasing order.

In the fourth testcase, there is a digit that comes after a letter — digit '1' after a letter 'c'.

解题说明：此题是一道模拟题，按照题目意思遍历字符串并判断是否满足题意即可。

#include<iostream>
#include<cstring>
using namespace std;

bool Is_Digit(char s)
{
	return s >= '0' && s <= '9';
}

bool Is_Letter(char s)
{
	return s >= 'a' && s <= 'z';
}

bool PassWord(string s, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		if (Is_Digit(s[i]) && Is_Digit(s[i + 1]))
		{
			if (s[i] > s[i + 1])
				return false;
		}
		if (Is_Letter(s[i]) && Is_Letter(s[i + 1]))
		{
			if (s[i] > s[i + 1])
				return false;
		}
		if (Is_Letter(s[i]) && Is_Digit(s[i + 1]))
			return false;
	}
	return true;
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		string s;
		cin >> s;
		if (PassWord(s, n))
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
	return 0;
}