311373: CF1976A. Verify Password

A. Verify Passwordtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 $t$ ($1 \le t \le 1000$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 20$) — the length of the password.

The second line contains a string, consisting of exactly $n$ 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.

ExampleInput

5
4
12ac
5
123wa
9
allllmost
5
ac123
6
011679

Output

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'.

题目大意：
Monocarp正在制作一个新的网站，目前面临的挑战是让用户选择强密码。Monocarp决定强密码应满足以下条件：
- 密码只能由小写拉丁字母和数字组成；
- 不能有字母后面的数字（即每个字母后面要么是另一个字母，要么是字符串的末尾）；
- 所有数字应按非递减顺序排列；
- 所有字母应按非递减顺序排列。

注意，密码可以只包含字母或只包含数字。

Monocarp实现了第一个条件，但他无法实现剩下的条件。你能帮助他验证密码吗？

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤1000）——测试案例的数量。
- 每个测试案例的第一行包含一个整数n（1≤n≤20）——密码的长度。
- 第二行包含一个由恰好n个字符组成的字符串。每个字符要么是小写拉丁字母，要么是数字。

输出：
- 对于每个测试案例，如果给定的密码是强的，则打印"YES"，否则打印"NO"。

示例：
输入：
```
5
4
12ac
5
123wa
9
allllmost
5
ac123
6
011679
```
输出：
```
YES
NO
YES
NO
YES
```

注意：
- 在第二个测试案例中，字母没有按非递减顺序排列。
- 在第四个测试案例中，有一个数字在字母'c'后面——数字'1'。题目大意： Monocarp正在制作一个新的网站，目前面临的挑战是让用户选择强密码。Monocarp决定强密码应满足以下条件： - 密码只能由小写拉丁字母和数字组成； - 不能有字母后面的数字（即每个字母后面要么是另一个字母，要么是字符串的末尾）； - 所有数字应按非递减顺序排列； - 所有字母应按非递减顺序排列。 注意，密码可以只包含字母或只包含数字。 Monocarp实现了第一个条件，但他无法实现剩下的条件。你能帮助他验证密码吗？ 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤1000）——测试案例的数量。 - 每个测试案例的第一行包含一个整数n（1≤n≤20）——密码的长度。 - 第二行包含一个由恰好n个字符组成的字符串。每个字符要么是小写拉丁字母，要么是数字。 输出： - 对于每个测试案例，如果给定的密码是强的，则打印"YES"，否则打印"NO"。 示例： 输入： ``` 5 4 12ac 5 123wa 9 allllmost 5 ac123 6 011679 ``` 输出： ``` YES NO YES NO YES ``` 注意： - 在第二个测试案例中，字母没有按非递减顺序排列。 - 在第四个测试案例中，有一个数字在字母'c'后面——数字'1'。