홀수 부분열

길이 $n$인 음이 아닌 정수 배열 $A$에 대해, 0개 이상의 원소를 지워서 얻을 수 있는 배열을 "부분열"이라고 한다.

배열 $A$의 부분열 $S$가 다음 조건을 만족하면 $S$를 $A$의 "홀수 부분열"이라고 정의한다.

• $S$의 원소의 합의 자릿수 중 홀수인 것들이 홀수이다.

음이 아닌 정수 배열 $A$를 입력받아 $A$의 서로 다른 홀수 부분열의 개수를 출력하시오. 단, 부분열의 원소를 정렬했을 때 그 결과가 같으면 같은 부분열로 취급한다.

$A = [3, 3, 6, 8, 6]$인 경우 정답은 8이다.

• 길이가 0인 홀수 부분열: 없음
• 길이가 1인 홀수 부분열: $[3]$
  • 합이 3이고, 자릿수 중 홀수가 3으로 하나
• 길이가 2인 홀수 부분열: $[3, 6]$, $[6, 6]$, $[6, 8]$
  • 합이 각각 9, 12, 14이고, 자릿수 중 홀수가 9, 1, 1로 하나씩
• 길이가 3인 홀수 부분열: $[3, 3, 6]$, $[3, 3, 8]$
• 길이가 4인 홀수 부분열: $[3, 3, 6, 6]$, $[3, 6, 6, 8]$
• 길이가 5인 홀수 부분열: 없음

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 10$).

각 테스트 케이스에 대해 첫 줄에 $A$의 길이 $n$이 주어진다. 둘째 줄에 $n$개의 0 이상의 정수가 공백으로 구분되어 주어진다. $A$의 각 원소는 0 이상 2,000 이하이다.

각 테스트 케이스에 대해 홀수 부분열의 수를 한 줄에 출력한다.

• 테스트 케이스 1: $\{3\}$, $\{3, 6\}$, $\{3, 3, 6\}$ 세 종류의 홀수 부분열이 있다.
• 테스트 케이스 2: $\{1\}$, $\{3\}$, $\{0, 1\}$, $\{0, 3\}$, $\{1, 2\}$, $\{2, 3\}$, $\{0, 1, 2\}$, $\{0, 2, 3\}$ 여덟 종류의 홀수 부분열이 있다.
• 테스트 케이스 3: 문제에서 서술한 대로 여덟 종류의 홀수 부분열이 있다.