As you may know, planets of Alpha Centauri (if they indeed do exist) would provide excellent conditions for intelligent life forms.

It is indeed true that there is a small Earthlike planet near Alpha Centauri, inhabited by a population of no particular significance. These humanlike creatures have much in common with us. Living in similar communities and having similar body structure and behavioral patterns, they unsurprisingly appreciate (approximately) the same time-killing activities as we do. One of these, the second most popular after Alpha Centauri Croquet, is the Alpha Centauri Tennis.

Although its rules differ from Earth Tennis, the two player version of Alpha Centauri Tennis resembles it in many ways. Same as Earth Tennis, it is played on a rectangular court divided into two parts by a net. Two players, standing on opposite sides of it, use a stringed racket to hit a ball back and forth to each other. There are certain rules how to hit the ball. The player who forces his opponent to violate one of these rules wins the current ball. The aim of both players is to win enough balls to win a game, enough games to win a set and enough sets to win the whole match. In the N player version of the Alpha Centauri Tennis a ball can be won by any one of the N players. Although technical details of this can be difficult to imagine, Alpha Centaurians are extremely inventive.

In the general N-player version, players serve in turns, following order determined before the match. Moreover, they shift when starting individual games and sets. For example, the players are A, B and C. They are ordered alphabetically. Player A serves the first ball of the first game. When the ball is won by one of the players, its B's turn to serve. After the game is won by one of the players, player B starts the second game. Finally, when the first set is won by someone, player B starts the second set. This repeats, always shifted by one player, until the match ends.

For three players the serving order looks as follows:

Set 1:

• Game 1: A, B, C, A, B, C ...
• Game 2: B, C, A ...
• Game 3: C, A, B ...
• Game 4: A, B, C ...
• ...

Set 2:

• Game 1: B, C, A, B ...
• Game 2: C, A, B ...
• Game 3: A, B, C, A ...
• ...

There are exact rules for counting the number of balls/games/sets won by a player.

RULES FOR WINNING A GAME

The state of a game can be described by assigning a non-negative number of points to each of the players. At the beginning of a game, the score of each player is zero.

Note: In Earth terminology, 0 points is called "love", 1 point is a "fifteen", 2 points is a "thirty", 3 points is a "forty" and 4 points is an "advantage". Be glad that you don't have to learn the Centaurian terminology :)

When a player P just won a ball, the new score is determined by using the first rule from the list that applies to the situation.

• If P currently has 3 points and no other player has more than 2 points, P wins the current game.
• If P currently has 4 points, he wins the game.
• If any other player currently has 4 points, that player loses one point. P gains a point.

RULES FOR WINNING A SET

The set is won by the first player that at the same time:

• won at least 6 games in this set,
• won at least 2 games more than any other player.

RULES FOR WINNING A MATCH

The winner is the first player to win at least three sets. A set in which no other player won a game counts as two won sets.

Problem specification

An observer from the Intergalactic Tennis Federation was watching a tournament in Alpha Centauri Tennis. Being unable to understand Alpha Centaurian language, he only managed to write down the winner of each ball. Now, for each match, knowing the sequence in which the players were winning the balls, he would like to somehow determine its winner.

Input

t - the number of test cases [t ≤ 150] than t test cases follows, each corresponding to one match. Each line contains the number of players N [N ≤ 10] and a string S consisting of uppercase letters [2 ≤ S ≤ 50000]. The players are represented by the first N letters of the English alphabet. If the i-th letter of S is X, it means the player X won the i-th ball from the begining of the match. You may assume that the match transcripts are correct and complete.

The order in which the players serve is the same as the order of their letters in the English alphabet.

Output

For each line, output a single character, being the letter of the player who won the corresponding match.

Example

Input:
1
3 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

Output:
B

(B has won two sets, each of them by winning 6 games, while A and C won none. Thus each of these sets counts as two and B has won the match.)

---

hide comments

< Previous 1 2 Next >
	emirau1: 2021-04-30 00:37:54 Erricto said this problem/solution in an interview with Joma Tech
	divyachowdary: 2019-08-20 04:10:31 can anyone explain me it's logic
	Stephen Oberholtzer: 2018-03-26 16:52:50 Am I misreading something? Rule 2 is "If P currently has 4 points, he wins the game." Rule 3 is "If any other player currently has 4 points, that player loses one point." and "P gains a point." Based on my reading of the rules, the first part of rule 3 could never activate, because as soon a a player reaches 4 points, the game ends and the next begins (with all players starting at zero).
	Bryan Poulsen: 2017-02-13 19:36:25 Most of the description is misleading. If you read the input rules it is much clearer what you need to do. If you print the last character of the S for each test case you will get AC.
	akshay31057: 2016-08-29 09:28:02 "knowing the sequence in which the players were winning the balls, he would like to somehow determine its winner" sufficient for the code.....
	rahul_verma: 2015-10-27 16:31:38 just one line code !!!!
	percy: 2015-10-20 15:22:58 I do not understand this statement "When a player P just won a ball, the new score is determined by using the first rule from the list that applies to the situation". Which "list" is this statement referring to?
	Christian López: 2015-10-20 05:22:59 Abstraction...
	scyth3r: 2015-07-08 08:46:05 Don't give a try....useless problem
	Bhuvnesh Jain: 2015-07-07 23:47:00 Hint: The input is such that there is always a valid result possible....