Solution 1: Binary Search

Let \(f(x)\) be the number of Neq Numbers less than or equal to \(x\). We are looking for the minimum \(x\) satisfying \(K \leq f(x)\). Since \(f(x)\) is monotonic with respect to \(x\), if \(f(x)\) can be calculated quickly, we can find the answer using binary search.

To calculate \(f(x)\), we consider the number of Neq Numbers \(y\) satisfying \(y < x + 1\), and categorize them based on the position of the digit where \(y < x + 1\) is determined. Let this be the \(k\)-th digit from the top. First, if the part of \(x\) above the \(k\)-th digit is not a Neq Number, there are zero such \(y\). If it is a Neq Number, the part of \(y\) above the \(k\)-th digit must be the same as \(x\).

Next, we consider the number of possibilities for the \(k\)-th digit and below. The number of choices for the \(k\)-th digit can be found by brute force. For the \((k-1)\)-th or lower digit, the only unusable number is the one in the digit immediately above it, so there are exactly nine possibilities. Therefore, there are \(d 9^k\) Neq Numbers \(y\) for which \(y < x + 1\) is determined at the \(k\)-th digit from the top, where \(d\) is the number of possibilities for the \(k\)-th digit.

By adding this up for all \(k\), we can calculate \(f(x)\) in \(O(\log x)\) time. Therefore, if \(M\) is an upper bound of the answer, we can find the answer in \(O(\log^{2} M)\) time per test case. For \(M\), the number of Neq Numbers with \(18\) digits is \(9^{18}\), which is larger than the upper limit of \(K\), so it is sufficient to use \(M=10^{18}\) or similar.