EALP1  Enough of analyzing, let’s play
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 i^{th} integer denotes the number of stones in the i^{th} 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:
20140106 03:44:00
@shiv prassad


shiv prasad chabarval:
20131220 21:35:38
i think here output value is always <= n


Manu Narsaria:
20130918 17:22:38
Give More test cases... 

007: Name stolen:
20130812 10:49:29
play xor!!!! 

ওয়াসী (Wasi):
20130509 15:43:10
Nice Problem! 

Andy:
20130110 11:21:28
not "than" but "then" 

Paul Draper:
20121120 06:14:15
@alphaplus, I also thought case 1 was 1 at first.


Samir Ahmed:
20120319 17:56:57
@alphaplus, why is the answer 1? 

alphaplus:
20120314 08:05:26
case 1 ans is 1


alphaplus:
20120314 07:45:15
nim sum 
Added by:  Samir Ahmed 
Date:  20120121 
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) 