Alice and Bob are playing a game. They have (n) cards numbered from (1) to (n). At the beginning of the game, some of these cards are given to Alice, and the rest are given to Bob. Card with number (i) beats card with number (j) if and only if (i > j), with one exception : card (1) beats card (n). The game continues as long as each player has at least one card. During each turn, the following occurs: Alice chooses one of her cards and places it face up on the table; Bob, seeing Alice's card, chooses one of his cards and places it face up on the table; if Alice's card beats Bob's card, both cards are taken by Alice. Otherwise, both cards are taken by Bob. A player can use a card that they have taken during one of the previous turns. The player who has no cards at the beginning of a turn loses. Determine who will win if both players play optimally. The first line contains a single integer (t) ((1 \le t \le 5000)) — the number of test cases. Each test case consists of two lines: the first line contains a single integer (n) ((2 \le n \le 50)) — the number of cards; the second line contains (n) characters, each either A or B . If the (i)-th character is A , then card number (i) is initially given to Alice; otherwise, it is given to Bob. Additional constraint on the input: in each test case, at least one card is initially given to Alice, and at least one card is initially given to Bob. For each test case, output Alice if Alice wins with optimal play, or Bob if Bob wins. It can be shown that if both players play optimally, the game will definitely end in a finite number of turns with one of the players winning. In the first test case, Alice has only one card, and Bob has only one card. Since Alice's card beats Bob's card, she wins after the first turn. In the second test case, Alice has only one card, and Bob has only one card. Since Bob's card beats Alice's card, he wins after the first turn. In the thi