DCEPCA01 - Good Luck

no tags 

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 0th to ith position in the number including positions 0 and i.
G(i) = the number of 7’s from 0th to ith 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 n-4 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 0th 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: 2014-02-07 13:52:26

very nice question...

Kartik Khare: 2013-05-26 12:31:34

ya i got it actually i was taking last digit as 0th digit

Last edit: 2013-05-26 12:31:48
Sandeep Pathry: 2013-05-26 09:55:04

@kartik its 1 buddy...
|1-2-3+3|=1

Kartik Khare: 2013-05-26 08:54:26

how can 4447 be a dynamic number the summation for it is 0.

Abhilash Kumar: 2012-12-17 16:47:37

@Tjandra Satria Gunawan thanks a lot..i dont know why but i didnt noticed it :)

(Tjandra Satria Gunawan)(曾毅昆): 2012-12-17 11:46:52

@Abhilash Kumar: You're wrong. h(i) never negative, because of absolute() function...

Last edit: 2012-12-17 11:47:11
Abhilash Kumar: 2012-12-17 11:37:37

8924=4447+4477
right..but submation(h(i)) for them are -1 .but if we use 7774 we get 1..i m wrong??

triveni: 2012-12-16 13:43:50

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

(Tjandra Satria Gunawan)(曾毅昆): 2012-12-07 09:03:46

thanks dce coders, I like most of your problem ;-)
so far 14 DCE problems solved :-D


Added by:dce coders
Date:2012-12-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C CPP C++ 4.3.2 CPP14-CLANG CPP14 COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem