H - Hold or Continue?

Languages: C, C++, Java, Python, ... (details)

Pig is a simple dice game for two or more players. Each turn, a player repeatedly rolls a dice until either a $1$ is rolled or the player decides to "hold":

• If the player rolls a $1$, they score nothing in their turn and it becomes the next player's turn.
• If the player rolls any other number, it is added to their turn total and the player can decide between hold'' or continue''.
• If the player chooses to hold'', their turn total is added to their score and it becomes the next player's turn. Otherwise the player continues rolling the dice.

The first player to score \emph{exactly} $75$ wins the game. If a player’s score plus their turn total exceeds $75$, they score nothing in their turn and it becomes the next player's turn.

Catelyn Tully is playing Pig with her father Hoster. If Catelyn begins her turn rolling a $5$, she could hold and score $5$ during her turn. If she chooses to continue and rolls a $2$, she could hold and score $7$. If she chooses again to continue and rolls a $1$, she must end her turn without scoring. If at his turn Hoster rolls the sequence $4$-$5$-$3$-$5$-$5$ and then he chooses to hold, he adds his turn total of $22$ to his current score (unless the sum exceeds $75$). Then Catelyn rolls the dice again, and so on, until one of them scores exactly $75$.

Hoster finds the game very didactic and he became a pretty good player. After playing several times with Catelyn, he realized that she is very impulsive and continues rolling the dice more times than she should. Catelyn would like to improve the way she plays, but unfortunately Hoster doesn't have too much patience to teach her, so she needs your help. While playing with her father, Catelyn has to decide several times whether to hold or continue, and sometimes she is not sure about what to do. Can you advise her so that each decision maximizes her winning probability?

Input

The first line contains an integer $Q$ ($1 \leq Q \leq 1000$) indicating the number of questions on which Catelyn wants your advice. Each of the next $Q$ lines describes a question with three integers $C$, $H$ and $X$ ($0 \leq C, H \leq 73$, $X \geq 2$, $C+X \leq 75$), representing respectively Catelyn’s current score, Hoster’s current score, and Catelyn’s turn total (sum of the rolls of the dice during her turn).

Output

Output $Q$ lines, each line with a character indicating the decision Catelyn must make for the corresponding question of the input, so as to maximize her winning probability if both Catelyn and Hoster play optimally. For each question, the character must be the uppercase letter "H" if the optimal decision is to hold, or the uppercase letter "C" if the optimal decision is to continue. It is guaranteed that  the optimal decision can be clearly differentiated; this means that $|p_h-p_c| > 10^{-5}$, where $p_h$ is the winning probability if Catelyn decides to hold, and $p_c$ is the winning probability if she decides to continue ($0 \leq p_h,p_c \leq 1$).

Sample test(s)

Input
3 15 0 3 35 50 40 15 0 30
Output
C H H