Склади числа

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