⑨运算(Hard Version)
题号：NC307906
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}本题为问题的困难版本，两题的唯一区别在于变量 x 的数据范围。

\hspace{15pt}CirnoNine 很喜欢数字 9，他认为只有数位上全是 9 的数字才是「好数字」（换句话说，一个正整数被称为「好数字」，当且仅当其十进制表示下的每一位数字均为 9）。

\hspace{15pt}现在，给定一个整数 x，你可以进行任意步操作，每一步操作从以下两种操作之一中选择一个执行：
\hspace{23pt}\bullet\,对该整数加 9，即 x\gets x+9。
\hspace{23pt}\bullet\,对该整数乘 9，即 x\gets 9 \times x，但是该操作至多使用一次。
\hspace{15pt}请问至少需要多少步，才能使得 x 变成一个「好数字」。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 10^4\right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}在一行上输入一个正整数 x\left(1\leq x\leq 10^{16}\right)，表示初始数字。

输出描述:

\hspace{15pt}对于每一组测试数据，新起一行。若无法变成「好数字」，则输出 -1，否则输出一个非负整数，表示最少需要的步数。
示例1

输入

复制 
8
2
8
101
16
999
182
981
111

输出

复制 
2
4
3
16
0
106
2
1

说明

\hspace{15pt}对于第一组测试数据，其中一种合法的方案为：2 \xrightarrow{+ 9} 11 \xrightarrow{\times 9} 99。

\hspace{15pt}对于第二组测试数据，其中一种合法的方案为：8 \xrightarrow{\times 9} 72 \xrightarrow{+ 9}81 \xrightarrow{+ 9}90 \xrightarrow{+ 9}99。

\hspace{15pt}对于第三组测试数据，其中一种合法的方案为：101 \xrightarrow{+ 9} 110 \xrightarrow{\times 9} 990 \xrightarrow{+ 9} 999。

\hspace{15pt}对于第七组测试数据，其中一种合法的方案为：981 \xrightarrow{+ 9} 990 \xrightarrow{+ 9} 999。