17059번 - 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.

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 ≤ 10¹⁸).

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