AKVOD06 - Cartman and Butters Game

Cartman and Butters are playing a simple game. They have ā€œNā€ boxes and each box has some amount of money inside it. The boxes are numbered as 1, 2 up to N. In each turn a player can remove a maximum of X(i) amount of money from box i. Initially the value of X(i) (1 <= i <= N) is ā€œZā€ for all the boxes. At any point a player can select the box i and a value K (1 <= K <= X(i)) and remove K amount of money from the box i and update the value of X(i) = K. That means at any point, the amount of money removed from the box can not exceed the amount of money removed from the same box previously. Now let us suppose that both the players play optimally and Cartman takes the first turn. If at any point a player can not remove any money from any box then he loses. Can you predict who will win the game?

Input

The first line will contain "T" the no. of test cases. Then "T" test cases follow. The first line of each test case will contain two integers "N" and "Z". The next line will contain "N" integers Ai (1 <= i <= N), where Ai denotes the amount of money in ith box.

Output

For each test case, print the name of winner "Cartman" or "Butters" in a separate line (without quotes).

Constraints

1 <= T <= 100
1 <= N <= 50
1 <= Z <= 10^4
1 <= Ai <= 1000

Example

Input:
4
1 1
2
2 2
3 3
4 8
3 8 5 10
5 10
8 5 10 20 15

Output:
Butters
Butters
Cartman
Cartman

Added by:Ankit Kumar Vats
Date:2014-02-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Self

hide comments
2019-01-28 03:36:15
i tried grundy number style approach, and it is WAAAAAAAAYYYY too slow now i have to figure out the right way to do it (though, i did not cache results, so in fact it was very inefficient, and i also didn't consider that permutations of one thing are all the same...)

Last edit: 2019-01-28 03:37:42
2014-05-18 20:48:38 Kanish_The_Vista
@Ankit Kumar Vats could you expalin me the last test case
2014-03-16 20:16:09 Bhavik
nice one:)
2014-02-25 19:45:48 Prasun Joshi
please explain the test cases
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.