You are given the following:

• Given a string S of N lower case alphabets.

Two players A and B play a game turn by turn in which one player can have either of the following moves in his turn:

1. Remove a consonant from the string.
2. If it is a vowel, then you may convert it to any other alphabet.

The player unable to make a move loses the game.

Task

Predict the winner of the game if both play optimally and A to start's the game. The game may end in a draw if the game may go on forever.

Note

• 'a', 'e', 'i', 'o' ,'u' are vowels and others are consonants in lowercase alphabets.

Example

Assumptions

• N = 2
• String S = "bc"

Approach

In 1st turn A will remove a consonant either 'b' or 'c'. In the 2nd turn, B will remove the remaining consonant left. In 3rd turn, nothing is left so A loses the game.

Function description

Complete the solve function provided in the editor. This function takes the following 2 parameters and returns the winner of the game if both play optimally:

• N: Represents the length of string S
• S: Represents the string S of length N

Input: 

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains an integer T denoting the number of test cases. T also denotes the number of times you have to run the solve function on a different set of inputs.
• For each test case:
  • The first line consists of a single integer denoting the value of N.
  • The second line consists of the string S.

Output

For each test case, print a single character A or B denoting the winner of the game. If there is a draw print D in a new line.
Constraints

$1 \le T \le 10^3 \\ 1 \le N \le 10^4$

Note: String consists of only lower case alphabets.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.