DCEPCA01  Good Luck
A number is called lucky if it consists of only digits 4 and 7 ie. 4, 7, 44, 47 are lucky numbers while 3, 45, 4478 are not lucky. For a given lucky number the functions F(i) and G(i) are defined as follows
F(i) = the number of 4’s from 0^{th} to i^{th} position in the number including positions 0 and i.
G(i) = the number of 7’s from 0^{th} to i^{th} position in the number including positions 0 and i.
Let H(i)= absolute(F(i)F(i+1)F(i+2)+F(i+3))
A "Dynamic Number" is a lucky number which has maximum of summation(H(i)) from i = 0 to n4 amongst all lucky numbers of length N.
Given a number N , you need to find out the sum of the two smallest Dynamic Numbers of length N.If only one Dynamic Number is possible, then only that number is the answer.
Note : Most significant bit is defined as the 0^{th} position of the number.
Constraints
0 < T <= 100
4 <= N <= 10^5
Input
It consists of T+1 lines. T denotes the number of test cases. Followed by T lines, each containing one number N.
Output
Output T lines, each containing a number as required.
Example
Input: 1
4
Output: 8924
hide comments
anurag garg:
20140207 13:52:26
very nice question... 

Kartik Khare:
20130526 12:31:34
ya i got it actually i was taking last digit as 0th digit Last edit: 20130526 12:31:48 

Sandeep Pathry:
20130526 09:55:04
@kartik its 1 buddy...


Kartik Khare:
20130526 08:54:26
how can 4447 be a dynamic number the summation for it is 0. 

Abhilash Kumar:
20121217 16:47:37
@Tjandra Satria Gunawan thanks a lot..i dont know why but i didnt noticed it :) 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121217 11:46:52
@Abhilash Kumar: You're wrong. h(i) never negative, because of absolute() function... Last edit: 20121217 11:47:11 

Abhilash Kumar:
20121217 11:37:37
8924=4447+4477


triveni:
20121216 13:43:50
Thanks dce coders, this problem tought me about the difference in fastness of putchar and printf.. :) 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121207 09:03:46
thanks dce coders, I like most of your problem ;)

Added by:  dce coders 
Date:  20121204 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ASM32GCC MAWK BC CCLANG C C++ 4.3.2 CPP CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JSMONKEY KTLN NIM OBJC OBJCCLANG OCT PICO PROLOG PYPY R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Own Problem 