Chef loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits **4** and **7**. For example, numbers **47**, **744**, **4** are lucky and **5**, **17**, **467** are not.

Chef also use term **“lucky sum”**. Lucky sum is an operation between two integers. Let the first integer is **A**, **A[i]** equals **i-th** digit of **A** (0-base numeration, from right to left) and the second integer is **B**, **B[i]** equals to **i-th** digit of **B**. Then the lucky sum of **A** and **B** is equal to **C**, **C[i] = max(A[i], B[i])**. If **i** is greater than or equal to size of integer, the **i-th** digit is equal to **0**. For example, the lucky sum of **47** and **729** equals **749**, the lucky sum of **74** and **92** and **477** equals **497**.

Chef has an array **W** of integers. Find a number of non-empty subsequences of **W** such that the lucky sum of integers in that subsequences is a lucky number.

Subsequence of **W** is created by erasing some number (probably zero) elements from **W**.

**Input**

First line contains one number **T**, number of test cases. Each test is formed as follows: first line contains integer **n** – number of integers in **W**, next line contains **n** integers – array **W** for corresponding test.

**Output**

For each **T** test cases print one integer – result for the corresponding test.

**Constraints**

1 <= **T** <= 10

1 <= **n** <= 50

1 <= **Wi** < 10^9

**Example**

Input:

2

2

4 7

3

43 87 44

Output:

3

2

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Net; using System.Runtime.InteropServices; using System.Collections; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { //Lucky Sum int[] integerArray = { 4, 7 }; //int[] integerArray = { 43, 87, 44 }; int maxLimit = (int)Math.Pow(2, integerArray.Length) - 1; int count = 0; for (int i = 1; i <= maxLimit; i++) { string binary = DecimalToBinary(i).PadLeft(integerArray.Length, '0'); ArrayList numList = new ArrayList(); for (int j = 0; j < binary.Length; j++) { if (binary[j] != '0') { numList.Add(integerArray[j]); } } if (IsLuckyNumber(LuckySum(numList))) { count++; } } Console.WriteLine("Number of combinations possible to yield lucky sum = " + count); } public static string DecimalToBinary(int num) { string rem = ""; while (num >= 1) { int quot = num / 2; rem += (num % 2).ToString(); num = quot; } // Reversing the value string bin = ""; for (int i = rem.Length - 1; i >= 0; i--) { bin = bin + rem[i]; } return bin; } public static bool IsLuckyNumber(int num) { for (int i = 0; i < num.ToString().Length; i++) { if (num.ToString()[i] != '4' && num.ToString()[i] != '7') { return false; } } return true; } public static int LuckySum(int num1, int num2) { int i = num1.ToString().Length - 1; int j = num2.ToString().Length - 1; string sum = ""; while (i >= 0 && j >= 0) { sum = Math.Max(int.Parse(num1.ToString()[i].ToString()), int.Parse(num2.ToString()[j].ToString())) + sum; i--; j--; } while (i >= 0) { sum = num1.ToString()[i] + sum; i--; } while (j >= 0) { sum = num2.ToString()[j] + sum; j--; } return int.Parse(sum); } public static int LuckySum(ArrayList numList) { if (numList.Count > 0) { int sum = 0; for (int i = 0; i < numList.Count; i++) { sum = LuckySum(sum, int.Parse(numList[i].ToString())); } return sum; } else { return -1; } } } }