AT_ndpc2026_p LIS

For a positive integer $ n $ , define $ f(n) $ as follows: - Let $ n $ have $ d $ digits in decimal representation. Define a sequence $ A = (A_1, \dots, A_d) $ of length $ d $ as follows: - $ A_i $ is the $ i $ -th digit from the left in the decimal representation of $ n $ . - Let $ f(n) $ be the length of the longest strictly increasing subsequence of $ A $ . For example, $ f(347) = 3 $ , $ f(1192) = 2 $ , $ f(10123456789) = 10 $ , and $ f(11111) = 1 $ . You are given a positive integer $ N $ . Count the number of positive integers $ x $ such that by repeatedly applying the operation $ x \to x + f(x) $ zero or more times, you can obtain $ N $ . You are given $ T $ test cases. Solve each of them.

The input is given from standard input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $

Print $ T $ lines. On the $ i $ -th line, output the answer for the $ i $ -th test case.

### Sample Explanation 1 For example, in the second test case, starting from $ x = 102 $ and repeatedly applying the operation $ x \to x + f(x) $ : - $ 102 \to 104 \to 106 \to 108 \to 110 $ we can obtain $ N = 110 $ . The only values of $ x $ satisfying the condition are $ x = 102, 104, 106, 108, 110 $ , so there are $ 5 $ in total. ### Constraints - $ 1 \leq T \leq 2 \times 10^4 $ - $ 1 \leq N \leq 10^{18} $ - All input values are integers