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 ith card are wi and 0.
Firstly, Mista puts these n cards to table one by one. For each card, the probability of the wi side to be upward is 12, 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 4s 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 2n 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≤T≤4), the number of test cases.
For each test case, the first line contains a single integer n(4≤n≤40), the number of the cards.
The second line contains n integers w1,…,wn(4≤wi≤44444444), the positive numbers on the cards.
Output
For each test case, output a single line with a single integer, the answer.