Start

2018-01-10 13:00 CET

...

End

2018-01-17 13:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -223 days 13:08:52

Time elapsed

168:00:00

Time remaining

0:00:00

Problem G
Terraced fields

Terraced fields with beautiful landscapes in Northwest Vietnam are popular destinations for tourists. At each terraced field selected as a tourist attraction, the local authorities build a staircase alongside the terraced field. The steps are numbered from $1$ to $n$ starting from the bottom of the hill. At steps divisible by $8$ (i.e. steps numbered $8, 16, 24$, etc.) and at the final step (i.e. ${n}^{th}$ step), the step number is stone engraved as a height indication for tourists. It is considered that $6$ and $8$ are lucky digits so people used a precious stone to specifically engrave these digits.

There is a tour that goes to a terraced field having $n$ steps. The price of the tour is the number of precious stone engraved digits on its steps.

For given $n$, your task is to determine the price of the tour.

Input

The input consists of several datasets. The first line of the input contains the number of datasets, which is a positive number and is not greater than $100000$. The following lines describe the datasets.

Each dataset is described by one line containing an integer $n$ $(1<n \leq {10}^{18})$.

Output

For each dataset, write out on one line containing the price of the tour.

Sample Input 1 Sample Output 1
4
9
32
56
18
1
2
4
3