Lucky Sum

Problem code: LUCKY3

All submissions for this problem are available.

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

Author: witua
Date Added: 21-11-2011
Time Limit: 5 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

cudn't get whatz meant by

kp25 @ 1 Jan 2012 03:09 PM
cudn't get whatz meant by subsequence..? plz any explain output of 1st example..??

can u pls explain the

sravansai @ 1 Jan 2012 03:31 PM
can u pls explain the examples....!!!

I doubt the problem

zjut_dd @ 1 Jan 2012 03:45 PM
I doubt the problem description. I just want to know the result of this data: 1 2 4 4. should be 2 or 3??

@kp25 @sravansai please read

hiroto_adm @ 1 Jan 2012 03:56 PM
@kp25 @sravansai please read the problem statement carefully and think about examples yourself. If the problem statement has ambiguities, you can indicate them.

@zjut_dd If W = {4, 4}, there

hiroto_adm @ 1 Jan 2012 04:00 PM
@zjut_dd If W = {4, 4}, there are 3 non-empty subsequences. Those are {4}, {4}, {4, 4}. And please don't write additional sample cases for the problem:)

does subsequence only contain

kewljerk @ 1 Jan 2012 05:22 PM
does subsequence only contain 2 no.s at a time. for 43,87,44 case there can be one more case {44,44,44} and also {43,44,44}. @admin please clarify. thanx!

@kewljerk Read the problem

hiroto_adm @ 1 Jan 2012 05:43 PM
@kewljerk Read the problem statement carefully. I think that the definition of subsequences of W is written in the problem statement clearly. If you think the problem statement has ambiguities, please indicate them.

thanx admin!

kewljerk @ 1 Jan 2012 05:53 PM
thanx admin!

can the answer exceed integer

avinash1 @ 1 Jan 2012 10:23 PM
can the answer exceed integer value?

I mean for case like 1 50 7 7

avinash1 @ 1 Jan 2012 10:48 PM
I mean for case like 1 50 7 7 7..50times the answer should be greater than integer or is there mod prime number operation? or did I misunderstand the question?

Statement does not say

witaliy_adm @ 1 Jan 2012 11:01 PM
Statement does not say anything about prime mod operation. Hence, the answer may exceed max integer value.

4 and 7 gives ans 3 but it

goelrinku @ 2 Jan 2012 02:07 AM
4 and 7 gives ans 3 but it must be 2 ans case-4,7 only

@goelrinku Read the problem

hiroto_adm @ 2 Jan 2012 02:21 AM
@goelrinku Read the problem statement carefully

Admin, is the answer the

sai16vicky @ 2 Jan 2012 09:53 AM
Admin, is the answer the number of distinct subsequences or the number of subsequences(allowing repetition)???

@admins: Shouldn't the answer

mr777 @ 2 Jan 2012 07:03 PM
@admins: Shouldn't the answer to the second test case be 1? Please verify.

@sai16vicky repetation is

hiroto_adm @ 2 Jan 2012 08:01 PM
@sai16vicky repetation is allowed. For example, if W = {4, 4}, there are 3 non-empty subsequences {4}, {4} and {4, 4}.

@mr777 The sample cases in

hiroto_adm @ 2 Jan 2012 08:02 PM
@mr777 The sample cases in the problem statement are correct.

I think there's an issue. The

bodmas @ 2 Jan 2012 09:06 PM
I think there's an issue. The problem statement says 'lucky sum is an operation between two integers'. Thismeans that in the first test case, the only possible lucky sum is max(4, 7) = 7. Therefore the result should be 1, not 3.

The lucky sum of the sequence

hiroto_adm @ 3 Jan 2012 08:23 AM
The lucky sum of the sequence A = {a1, a2, a3, ..., an} is defined as follows: If n=1, the lucky sum is a1, otherwise the lucky sum is a1 + (a2 + (a3 + ... + (an-1 + an) ... ), where + denotes the lucky sum operator.

what is meaning

mak_zed @ 3 Jan 2012 07:39 PM
what is meaning of "Subsequence of W is created by erasing some number (probably zero) elements from W."?

Imagine that you have some

witaliy_adm @ 3 Jan 2012 07:58 PM
Imagine that you have some sequence of apples and you call it W. If somebody stole some apples (any number) then the rest of apples will create a subsequence of W. Sequence W is also a subsequence of W. :)

@mak_zed The definition of

hiroto_adm @ 3 Jan 2012 08:26 PM
@mak_zed The definition of subsequence is standard one. You can also see http://en.wikipedia.org/wiki/Subsequence

"If i is greater than or

umangkedia @ 6 Jan 2012 09:08 AM
"If i is greater than or equal to size of integer, the i-th digit is equal to 0". Which integer are you talking about??

@umangkedia It means that

hiroto_adm @ 6 Jan 2012 09:54 AM
@umangkedia It means that A[i] = 0 if (the number of digits of A) <= i. For example, if A = 47, then A[0] = 7, A[1] = 4, A[2] = 0, A[3] = 0, ....

where is this problem added

ikercasillas @ 21 Jan 2012 08:03 PM
where is this problem added in the practice solution.i wan't to test my solution.admin please see into it.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions