Склади числа
Limits: 2 sec., 512 MiB
У Марічки є улюблене число \(n\), яке має довжину \(len\) у десятковому записі. Марічка любить складати всі числа від 1 до \(n\) з рівно \(len\) кубиків. Якщо число, яке зараз складає Марічка має менше ніж \(len\) цифр, то вона додає ведучі нулі.
Марічка попросила зробити Зеника такі кубики, щоб вона могла скласти будь-яке число від 1 до \(n\). Кожен з кубиків має 6 граней і Марічка може обирати будь-яку підмножику з \(len\) кубиків та розставляти їх в довільному порядку та орієнтації.
Зеник дуже лінивий, тому хоче зробити якнайменше кубиків. Яка мінімальні кількість кубиків потрібна, щоб могти скласти всі числа?
Зауважте, що кубик з цифрою \(6\), можна перевернути догори ногами і отримати \(9\).
Input
В першому рядку задано одне ціле число \(t\) — кількість тестів.
В кожному з наступних \(t\) рядків задано по одному цілому числу \(n\).
Output
В \(t\) рядках виведіть мінімальну кількість кубиків для відповідного \(n\).
Constraints
\(1 \le t \le 10^4\),
\(1 \le n \le 10^{18}\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 1 4 6 7 | 1 1 1 2 |
| Input (stdin) | Output (stdout) |
|---|---|
| 2 31 47 | 2 3 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|