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.