Two players, S and T, are playing a game where they make alternate moves. S plays first. In this game, they start with an integer N . In each move, a player removes one digit from the integer and passes the resulting number to the other player. The game continues in this fashion until a player finds he/she has no digit to remove when that player is declared as the loser. With this restriction, its obvious that if the number of digits in N is odd then S wins otherwise T wins. To make the game more interesting, we apply one additional constraint. A player can remove a particular digit if the sum of digits of the resulting number is a multiple of 3 or there are no digits left. Suppose N = 1234. S has 4 possible moves. That is, he can remove 1, 2, 3, or 4. Of these, two of them are valid moves.
The other two moves are invalid. If both players play perfectly, who wins?
The first line of input is an integer T (T < 60) that determines the number of test cases. Each case is a line that contains a positive integer N . N has at most 1000 digits and does not contain any zeros.
For each case, output the case number starting from 1. If S wins then output ‘S’ otherwise output ‘T’.
範例輸入 1
3 4 33 771
範例輸出 1
Case 1: S Case 2: T Case 3: T
Pro 專屬功能： 查看這題在歷屆 CPE 出現過幾次 — 升級以解鎖.