spoj#DCEPCA01. Good Luck
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 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