Rikka with Mista

Problem Description

Rikka is a fervent fan of JoJo's Bizarre Adventure. As the last episode of Golden Wind has been aired, Rikka, with the help of Yuta, sets up this problem to express the love to Mista. Mista's lucky number is $4$. Today, Mista wants to test his luck with $n$ magic cards: For each card, there is a non-negative integer on each side. The two numbers on the $i$th card are $w_i$ and $0$. Firstly, Mista puts these $n$ cards to table one by one. For each card, the probability of the $w_i$ side to be upward is $\frac{1}{2}$, and these probabilities are independent with each other. As a result, there are $n$ integers on the table. Mista then sums up all these integers and counts the number of $4$s in the decimal representation of this sum: He uses this result to measure his luckiness. Since it's possible for each side of each card to be upward, there are $2^n$ possible states in total. You are required to calculate the sum of the results for all these situations.

Input

The first line of the input contains a single integer $T(4 \leq T \leq 4)$, the number of test cases. For each test case, the first line contains a single integer $n(4 \leq n \leq 40)$, the number of the cards. The second line contains $n$ integers $w_1, \dots, w_n(4 \leq w_i \leq 44444444)$, the positive numbers on the cards.

Output

For each test case, output a single line with a single integer, the answer. Hint There are $44$ $4$s in the sample input. Mista would like this sample input. In the first test case, there is $1$ state with the sum equal to $0$; $4$ states with the sum equal to $4$; $6$ states with the sum equal to $8$; $4$ states with the sum equal to $12$ and $1$ state with the sum equal to $16$. Therefore, there are only $4$ situations with the result equal to $1$ while on other cases, the result is $0$. So the answer should be $4$.

Sample Input

4

4

4 4 4 4

4

4 4 44 44

4

4 44 44 4444

4

444 44444 44444 4444444

Sample Output

4

10

24

38

Source

2019 Multi-University Training Contest 9