You play the game of rock-paper-scissors (for those who don't know it, you and your opponent show signs of rock/paper/scissors at the same time; rock beats scissors, scissors beat paper and paper beats rock; you score a point if your sign beats the opponent's signs) against a little kid. The winner is the first one to gain 3 points. Kids usually play in a simple manner - they think that they randomly choose either of the signs, but experience shows that unconsciously, people tend to choose scissors most often for the first game (a 'game' here is showing one sign and possibly getting one point, not a sequence of showing signs until one of you gets 3 points). Other than that, the kid's choice is random.

So, you get a sequence of last N<=1000000 games (note that, by definition, it's possible for no one to score a point during a game), and have to choose the sign you have to show to have the greatest chance of winning the next game.

You can assume there will be only one best choice (the one when you're most likely to win the next game), and that no one has scored 3 points yet in this game.

Input

On the first line, there is the number of test cases (t <= 10). For every test case, there is a number N, and N lines, each containing your sign and your opponent's sign from one past game.

Output

Read out a string, which is this time strictly from the set {"rock","paper","scissors"}, denoting your sign for the next game.

Example

Input:
1
0

Output:
rock

(obviously, if your opponent is most likely to start with scissors, you want to start with rock)