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