Meena and Razu have been playing Shaat Chara for many years. But they think the game is too violent. So, they came up with a new game. In this game, instead of just 1 pile, they start with n piles of stones. The game is for two players. Each player takes turn alternatively. In each turn a player can select any of the piles that has at least 1 stone left, and then remove some stone (at least one) from it. The game goes on like this until there are no stones left. The player who can’t make a move loses.

At first, Razu was very happy because there was no chance of injury in this game. But he quickly grew frustrated, because Meena was winning all the games. Meena is very clever. She always plays optimally. That means, if there is a chance to win, she will always win. So, Razu came to you with a particular state of the game. He wants to know how many possible moves he may take such that Meena’s win is not guaranteed.

Input

In a single line, you will be given T, the number of test cases.

T test cases follow. In each test case, you will be given n, the number of piles. Then in a single line, you will be given n numbers a_i, the number of stones in the ith (1 <= i <= n) pile.

Output

You have to print the case number first in the form “Case 1: ”.

For each case you have to print only the number of winning moves from that particular state of the game. See sample for clarification.

T <= 100

1 <= n <= 10000

1 <= a_i <= 100000

Note: Note that, winning moves mean the moves that will lead Meena to a losing state. For example, if the current state is {1, 3}, Razu can remove 2 stone from the second pile, which is a winning state. Because this move will lead to the state {1, 1}. Then Meena will remove 1 stone from any pile, and Razu will remove the other in the next turn. And Meena will lose the game, because there will be no remaining stone. But if Razu removed only 1 stone from the second pile, that will lead to the state {1, 2}, which is a winning state for Meena. Thus Meena will win.

Example

Input:
3
1
1
2
1 1
3
1 1 1

Output:
Case 1: 1
Case 2: 0
Case 3: 3