Problem AE
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}^\textrm {th}$ step), the step number is stone engraved as a height indication for tourists. The digits $6$ and $8$ are considered lucky, 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 $100\, 000$. 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, output the price of the tour.

4
9
32
56
18

1
2
4
3