Stephen Cook

Stephen Arthur Cook is a computer scientist and mathematician who works on complexity theory. He gave a precise statement of the P versus NP problem in the paper "The complexity of theorem-proving procedures", and he proved that the boolean satisfiability problem, SAT, is NP-hard. He won the Turing Award in 1982.

Cook and Levin play a game on a boolean formula. Every variable of the formula starts undecided. The two players move in turns and Cook moves first. On a turn, a player picks one undecided variable and fixes it to true or false. Once every variable has a value, Cook wins if the formula is true, and Levin wins if it is false.

Both players play optimally. Decide who wins.

The first line contains an integer $T$ ($1 \le T \le 20$), the number of test cases. Each test case takes two lines.

The first line of a test case contains an integer $n$ ($1 \le n \le 10$), the number of variables in the formula. The $i$-th variable is written as the $i$-th uppercase letter of the English alphabet, so the first variable is A and the third variable is C.

The second line contains a boolean formula of at most 256 characters. A boolean formula has one of these five forms.

• var, where var is a variable.
• ( formula1 ), where formula1 is a boolean formula.
• not formula1, where formula1 is a boolean formula.
• formula1 or formula2, where formula1 and formula2 are both boolean formulas.
• formula1 and formula2, where formula1 and formula2 are both boolean formulas.

Blanks separate the variables from the operators. There are four operators: and, or, not, and the brackets (). The first three are written in lower case. Precedence from high to low is (), then not, then and, then or.

For each test case, print the name of the winner on its own line, either Cook or Levin.