Odd Subsequence

For an array $A$ of $n$ nonnegative integers, a "subsequence" is any array obtained by deleting zero or more elements.

A subsequence $S$ of $A$ is called an "odd subsequence" of $A$ if it satisfies the following condition:

• The number of odd digits in the sum of the elements of $S$ is odd.

Given an array $A$ of nonnegative integers, output the number of distinct odd subsequences of $A$. Two subsequences are considered the same if sorting their elements yields the same result.

For $A = [3, 3, 6, 8, 6]$, the answer is 8.

• Odd subsequences of length 0: none
• Odd subsequences of length 1: $[3]$
  • The sum is 3, and the only odd digit is 3
• Odd subsequences of length 2: $[3, 6]$, $[6, 6]$, $[6, 8]$
  • The sums are 9, 12, 14, each with exactly one odd digit: 9, 1, 1
• Odd subsequences of length 3: $[3, 3, 6]$, $[3, 3, 8]$
• Odd subsequences of length 4: $[3, 3, 6, 6]$, $[3, 6, 6, 8]$
• Odd subsequences of length 5: none

The first line contains the number of test cases $T$ ($1 \le T \le 10$).

For each test case, the first line contains the length $n$ of $A$. The second line contains $n$ nonnegative integers separated by spaces. Each element of $A$ is between 0 and 2,000 inclusive.

For each test case, print the number of odd subsequences on one line.

• Test case 1: there are three odd subsequences: $\{3\}$, $\{3, 6\}$, $\{3, 3, 6\}$.
• Test case 2: there are eight odd subsequences: $\{1\}$, $\{3\}$, $\{0, 1\}$, $\{0, 3\}$, $\{1, 2\}$, $\{2, 3\}$, $\{0, 1, 2\}$, $\{0, 2, 3\}$.
• Test case 3: as described in the problem, there are eight odd subsequences.