CSHOWH - Sachin Loves Boundaries

no tags 

Sachin loves to hit boundaries. His lucky digits are 4 and 6. A lucky number is one which has its last digit lucky. 144, 124, 156 are lucky numbers while 111, 123, 667, 249 are not lucky. Given a number he wants to find the minimum of summands which are lucky numbers, necessary to produce a sum equal to the given number.

If it's not possible, print -1.

Input

Each file will consist of a number of test cases T. Each test case will consist of only one number N in one line.

Output

Print the least number of lucky summands as given in the question. If it's not possible, print -1.

Constraints

T <= 100000 (10^5)
N <= 10^18

Example

Input:
1
10

Output:
2

Explanation

For the first case: 10 = 6 + 4. So, we need only two lucky numbers.


hide comments
Mitch Schwartz: 2013-11-01 17:43:36

Moved to tutorial.

Raushan Kumar: 2013-11-01 17:08:50

very very easy :)

Martijn Muijsers: 2013-11-01 14:41:22

Less tricky than I thought at first. Easy but good problem!

રચિત (Rachit): 2013-10-31 22:36:14

Tutorial!


Added by:Aradhya
Date:2013-10-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeShow IIIT Allahabad