本题为问题的困难版本，两题的唯一区别在于变量 的数据范围。 CirnoNine 很喜欢数字 ，他认为只有数位上全是 的数字才是「好数字」（换句话说，一个正整数被称为「好数字」，当且仅当其十进制表示下的每一位数字均为 ）。 现在，给定一个整数 ，你可以进行任意步操作，每一步操作从以下两种操作之一中选择一个执行： 对该整数加 ，即 。 对该整数乘 ，即 ，但是该操作至多使用一次。 请问至少需要多少步，才能使得 变成一个「好数字」。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：在一行上输入一个正整数 ，表示初始数字。

输出描述:

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