HC - Happy Coins


A line of coins are given, some belongs to lxh while others belongs to hhb. Now the two guys are about to play a game. In every round of game, each player can select any two consecutive coins and change them into one coin, if the two coins belongs to the same person, the new one will be gained to hhb, or else it will belongs to lxh. The two guys take turns playing this game, lxh always play first. The game runs round by round. You can easily make sense that we will get only one coin at the end of game. Now the question is, suppose the two players perform optimally in the game, which person does the final coin belongs to?

Input

The first line of the input contains one integer T, which indicate the number of test cases.

Following each test, the first line contains an integer N (N ≤ 105), the number of coins. Following N lines, each line contains a name, lxh or hhb, the name of whom this coins belongs to.

Output

For each case, output a line contains the name of whom the final coin belongs to.

Example

Sample Input
1
2
lxh
hhb

Sample Output
lxh

hide comments
Luis Manuel Díaz Barón: 2021-03-31 23:05:39

I personally don't get this description, what does this suppose to mean:
"the new one will be gained to hhb, or else it will belongs to lxh", is gain the same of belong? does the guy put the new coin back to the table or does he put it into a poket... if I take two consecutive coins will it generate a gap??
It seems its just me but this text is like a riddle.

Last edit: 2021-03-31 23:06:16
prabhav_123: 2019-01-01 19:58:35

***heavy spoilers ahead***

kalyanavuthu: 2017-11-07 16:54:26

NO need to of bit, no critical thinking , only the ability to check "even " or "odd" is sufficient

ak_cruiser: 2017-06-21 01:44:18

the more you think ,the more you can get confused....but after getting the solution you'll be amazed how this simple the logic is.

mhto: 2017-03-18 15:45:21

wrote hbb instead of hhb. got wrong answer once :D

gautam: 2017-02-22 15:07:33

easy :)

sachinsharma12: 2017-01-20 06:18:53

Simple +,-....
Easy one

kass_97: 2017-01-12 21:04:24

Easyyyy....AC in one go

gkr007: 2016-06-05 09:15:02

simple "BIT"

lalit_nit: 2016-01-25 17:39:07

Do Play with Balls after that or before that.... two AC at once :P


Added by:Kumar Anurag
Date:2010-06-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:TJU