Big Coefficients

F(x) is a polynomial in x with integer coefficients, here F(x) = (1+x)^a1 + (1+x)^a2 + ... + (1+x)^am. Given a1, a2, ... , am, find number of odd coefficients of F(x).

The first line contains a single positive integer T( T <= 10000 ), indicates the number of test cases.
For each test case:
First line contains an integer N(1 <= N <= 15).
Second line contains N integers a1, a2, ..., am ( 0 <= ai <= 2^45 )

For each test case: output the case number as shown and an the odd coefficients of F(x).

4
1
1
1
3
2
1 3
3
1 2 3

Case #1: 2
Case #2: 4
Case #3: 2
Case #4: 2

Case #3: (1+x) + (1+x)^3 = 2 + 4x + 3x^2 + x^3. it contains 2 odd coefficients.
Case #4: (1+x) + (1+x)^2 + (1+x)^3 = 3 + 6x + 4x^2 + x^3. it contains 2 odd coefficients.

2011 Multi-University Training Contest 9 - Host by BJTU