Problem Description
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).
Input
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 )
Output
For each test case: output the case number as shown and an the odd coefficients of F(x).
Sample Input
4
1
1
1
3
2
1 3
3
1 2 3
Sample Output
Case #1: 2
Case #2: 4
Case #3: 2
Case #4: 2