To add or to multiply game

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef and his brother Chefu are playing a game with a sequence of N integers.
They take alternate turns to play. In each turn, the player should choose two adjacent integers from the sequence, remove them, and put in their place either their sum or their product. So if the sequence is (5,17,2,4,102), then one valid move would be to select 2 and 4, and replace them with their product, which is 8. So the sequence now becomes (5,17,8,102). They could also have been replaced by their sum, and in that case, the new sequence would become (5,17,6,102).
The game continues until there's only one integer left in the sequence. If this integer is even, then Chef is the winner, otherwise Chefu is the winner.
Given the initial sequence and the player who will play the first turn, you should tell who is going to win the game assuming that both of them play optimally.
Input
The first line of the input contains an integer T denoting the number of test cases.
First line of each testcase contains N, the length of the initial sequence. and a string which is either "Chef" or "Chefu" denoting who will play first.
The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the initial sequence.
Output
For each test case, output a single line containing who will win the game: "Chef" or "Chefu".
Constraints
 1 ≤ T ≤ 10,000
 1 ≤ N ≤ 100,000
 sum of N in all testcases will not exceed 100,000
 1 ≤ A_{i} ≤ 50
Example
Input: 2 1 Chef 8 3 Chef 1 2 3 Output: Chef Chefu
Explanation
Test case 1: The game stops as soon as it begins, because there is only one integer, and because it is even, Chef wins.
Test case 2: Chef has 4 valid first moves:
 Add 1 and 2, and change the sequence to (3,3). Now Chefu will multiply these two, and get 9, and win, because only one integer is left, and it is odd.
 Multiply 1 and 2, and change the sequence to (2,3). Now Chefu will add these two, and get 5, and win, because only one integer is left, and it is odd.
 Add 2 and 3, and change the sequence to (1,5). Now Chefu will multiply these two, and get 5, and win, because only one integer is left, and it is odd.
 Multiply 2 and 3, and change the sequence to (1,6). Now Chefu will add these two, and get 7, and win, because only one integer is left, and it is odd.
As we can see, for every possible move of Chef, Chefu has a move that lets him win. Hence, in optimal play, Chefu will win.
Author:  kingofnumbers 
Tester:  errichto 
Editorial  https://discuss.codechef.com/problems/ADDMULT 
Tags  adhoc, cook79, gametheory, kingofnumbers, medium 
Date Added:  20102016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 