XOR

XOR or Exclusive OR (often written with symbol ⊕) is one of the basic binary operator for computer. It takes two inputs and produces one output, just like AND (symbol &) and OR (symbol |). If two bits are XORed, the results will be:

  A  B   A ⊕ B
  0  0  -  0
  0  1  -  1
  1  0  -  1
  1  1  -  0

In other word, if two bits have the same value then the output is 0, otherwise it's 1.

For example, 25 ⊕ 12 = 21.

   25 = 1 1 0 0 1
   12 = 0 1 1 0 0
   -------------- ⊕
   21 = 1 0 1 0 1

The binary representation of 25 is 11001 and 12 is 1100. If we XOR 25 and 12, we will get 21 (10101).

As a side note, both C/C++ and Java have this binary XOR operator and they used caret symbol (^), e.g., 25 ^ 12 .

Binary operator XOR satisfies both the property of being commutative, A ⊕ B = B ⊕ A, and the property of being associative, A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C. Therefore, if we have a list of integers and XOR all of them (in any arbitrary order), we will get a same single integer. This single integer is often referred as the XOR value. For example, let S = {15, 20, 4, 7}, then the XOR value of S is 15 ⊕ 20 ⊕ 4 ⊕ 7 = 24. You can XOR S in any order you like and you will always get the same value, which is 24.

In this problem, you are given a list of N non-negative integers S; your task is to determine how many continuous subsequence of the list which XOR value is equal to zero.

Input

The first line of input contains an integer T (1 ≤ T ≤ 100) the number of cases. Each case begins with one integer N (1 ≤ N ≤ 20,000) in a line. The next line contains N integers A_i (0 ≤ A_i ≤ 2³¹-1) in a line each separated by a single space. These numbers represent the given list S.

Output

For each case, output in a line the "Case #X: Y" where X is the case number starts from 1, and Y is the number of continuous sub-sequence of S which XOR value is equal to zero.

3
4
15 40 4 7
3
0 0 0
7
5 4 1 11 10 3 2

Case #1: 0
Case #2: 6
Case #3: 4

Explanation for the 3^rd sample input.

There are 4 continuous sub-sequences which XOR value are zero:

• 1^st to 3^rd element: 5 ⊕ 4 ⊕ 1 = 0.
• 1^st to 7^th element: 5 ⊕ 4 ⊕ 1 ⊕ 11 ⊕ 10 ⊕ 3 ⊕ 2 = 0.
• 3^rd to 5^th element: 1 ⊕ 11 ⊕ 10 = 0.
• 4^th to 7^th element: 11 ⊕ 10 ⊕ 3 ⊕ 2 = 0.