Soha and Tara have stopped playing the game “mouse and cheese” which they invented few months ago. One of the main reasons for discontinuing this game is that it involves a mouse — (Tara is scared of anything that has four legs and can move). Since Tara is fond of playing games, Soha came up with, yet, another game that only involves a pen and a paper. This new game is called “Prime Game”. Initially Soha writes a list of N integers on a piece of paper. It’s a two player game where the players make moves alternately. Soha, being player 1, goes first. The rules of this game are described below. • In each move a player has to remove one or move contiguous numbers either from left or right from the list. In his/her turn a player can say “pass” — which means he/she doesn’t have to remove any numbers in that move. However, a player can pass at most K times. • The sum of these removed integers has to be a prime number. Prime numbers are positive integers that have exactly two distinct factors. So the first few prime numbers are 2 3 5 7 11 13 ... • The number 42 is special and can take any value that the player chooses. For example, a player can remove the integers {4 10 42} in one move; if 42 is treated as 3, then sum equals to 17 — which is a prime number. • If a player uses up all his/her “passes” and doesn’t have any valid move, then he/she is declared as the loser. If both the players play perfectly, who wins? Input The first line of input file is an integer, T (T < 100) that indicates the number of test cases. Each case starts with 2 integers N (0 < N < 100) and K (0 ≤ K < 1000). The meanings of these are mentioned above. The next line contains N space separated integers that Soha initially writes. Each of these integers will be in the range [−1000, 1000]. Output For each case, output the case number first followed by the name of the player who wins. Look at the sample for exact format. Sample Input 3 30 333 30 444 52 12345
2/2 Sample Output Case 1: Soha Case 2: Tara Case 3: Soha