题目描述

该题目为数数 ( Easy ) 的困难版本，其中只有 n 的数据范围更大，数数 ( Easy ) 的解一定是数数 ( Hard )的子集，即数数 ( Hard )的代码一定能通过数数 ( Easy )。

某一天，工作室需要统计人数，让小劉来帮忙数，但是由于小劉数学极差，因此他数数的时候总是会忘记数 8 ，就是他数完 7 以后，就会直接数 9 。 更准确的说直就是数字 n 中的每一位都不会出现8。

最后小劉数错了人数，需要你帮助小劉纠正数数的问题，给出正确的结果 N 。

输入描述

第一行一个正整数 T ( 1 <= T <= 10³ ) 表示数据组数。

每组测试数据描述如下：

第一行一个正整数 n ( 1 <= n <= 10¹⁸ ), n 表示数字的大小。

保证所有组数据中的 n 每一位均不会出现 8 。

输出描述

求出每一组数据的正确结果 N 。

样例

2
10
90

9
72

解释

对题目中样例的解释：

第一个，小劉数到了10，但是因为小劉数过7之后，就直接开始数9，所以跳过了8，少数了一个数字，就输出 9 。

第二个，小劉数到了90，但是在数到7，17，27，37，47，57，67，77，都会跳过8，18，28，38，48，58，68，78，所以这样会少数 8 。

但是当跳过78后，开始数79，正常会数80，但是小劉会跳过数字8，所以会直接数到90，这样又会少数 10 。

因此总共少数12个数，那么纠正后的数数结果就是72，输出72即可。

限制范围

每个测试样例限制为1s, 248Mb。