Next Journal ID Generator

The task is to generate the next smallest lexicographically valid ID for a diary entry. You are given an ID of fixed length N consisting of uppercase English letters. The next valid ID is obtained by incrementing the rightmost character that is not 'Z' by one and setting all characters to its right to 'A'. If every character of the ID is 'Z', then the next valid ID is a new ID with length N+1 consisting entirely of 'A's.

For example, given the ID AAC of length 3, the next ID is AAD. Similarly, for an ID AZZZ of length 4, the output should be BAAA, and if the input is ZZZ (all Zs) then the output is AAAA (length 4).

inputFormat

The first line of input contains an integer T representing the number of test cases. Each test case consists of two lines:

• The first line contains an integer N, the length of the current diary ID.
• The second line contains a string P, the current diary ID.

All input is read from standard input.

outputFormat

For each test case, output a single line containing the next lexicographically valid diary ID. All output should be written to standard output.## sample

3
3
AAC
4
AZZZ
2
AB

AAD
BAAA
AC