EALP1 - Enough of analyzing, let’s play

no tags 

All of must you know the game of Nim. For those who don’t know, I will describe the game in brief:

There are two players and there are N piles. Each pile contains some stones. Player 1 takes the first turn, than player 2, than again player 1 and so on. At each turn, the player chooses any ONE pile, and removes at least one stone from it. The player who makes the last move wins.

Now given N piles, your task is to find the number of ways Player 1 can start the game so that after his first move, he is in the winning position.  That means after Player 1 has removed some stones from any ONE pile, he will surely win the game if he plays optimally no matter how well Player 2 plays the game.

Input

Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with an integer N (1 ≤ N ≤ 1000). The next line contains N integers all less than 1000. The ith integer denotes the number of stones in the ith pile.

Output                                       

For each case, print the desired result. 

Example

Input:

2

3

11 15 8

3

11 15 7

Output:

Case 1: 3

Case 2: 3


hide comments
darryl: 2014-01-06 03:44:00

@shiv prassad
you do realize that you have to print like "Case 1: 3", right?
not just 3?

Last edit: 2014-01-06 03:44:48
shiv prasad chabarval: 2013-12-20 21:35:38

i think here output value is always <= n
but don't know why i m getting WA somebody plz help my code
thanku darry :)

Last edit: 2014-02-03 19:56:31
Manu Narsaria: 2013-09-18 17:22:38

Give More test cases...

007: Name stolen: 2013-08-12 10:49:29

play xor!!!!

ওয়াসী (Wasi): 2013-05-09 15:43:10

Nice Problem!

Andy: 2013-01-10 11:21:28

not "than" but "then"

Paul Draper: 2012-11-20 06:14:15

@alphaplus, I also thought case 1 was 1 at first.

An explanation of the test cases:
After the first player's turn he could force the second player into the losing situations...
Case 1 - (7,15,8) or (11,3,8) or (11,15,4)
Case 2 - (8,15,7) or (11,12,7) or (11,15,4)

Samir Ahmed: 2012-03-19 17:56:57

@alphaplus, why is the answer 1?

alphaplus: 2012-03-14 08:05:26

case 1 ans is 1

alphaplus: 2012-03-14 07:45:15

nim sum


Added by:Samir Ahmed
Date:2012-01-21
Time limit:1s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem (Samir's Contest 2 @Lightoj)