Terraced fields
Time limit8sMemory limit512 MB
Count how many digit characters are 6 or 8 in the decimal numbers written on steps divisible by 8 plus the final step n.
- Level
Medium4 of 10
- Topics
- Math, Implementation, Brute force, Combinatorics
- Solved
- No attempts yet
Problem
The terraced fields of Northwest Vietnam, known for their beautiful scenery, are popular destinations for tourists. At each terraced field designated as a tourist attraction, the local authorities built a staircase alongside the field. The steps are numbered from 1 to n starting from the bottom of the hill. At every step divisible by 8 (that is, steps 8, 16, 24, and so on) and at the final step (the nth step), the step number is engraved in stone as a height indication for tourists. Since 6 and 8 are considered lucky digits, people used a precious stone to engrave specifically these digits.
There is a tour that visits a terraced field with n steps. The price of the tour is the number of precious stone engraved digits on its steps.
Given n, determine the price of the tour.
Input
The input consists of several datasets. The first line contains the number of datasets, which is a positive integer not greater than 100,000. The following lines describe the datasets.
Each dataset is given on one line containing an integer n (1 < n ≤ 10^18).
Output
For each dataset, print the price of the tour on one line.