AT_ndpc2026_p LIS

正整数 $ n $ に対して $ f(n) $ を以下の手順によって得られる整数とします。 - $ n $ が $ 10 $ 進表記で $ d $ 桁であるとする。長さ $ d $ の数列 $ A=(A_1,\dots,A_d) $ を以下のように定める。 - $ A_i $ は「 $ n $ の $ 10 $ 進表記を文字列とみなした時の左から $ i $ 文字目の数字」を数とみなした値である。 - $ A $ の最長狭義増加部分列の長さを $ f(n) $ とする。 例えば $ f(347) = 3, f(1192) = 2, f(10123456789) = 10, f(11111) = 1 $ です。 正整数 $ N $ が与えられます。 正整数 $ x $ であって、 $ x $ を $ x+f(x) $ に変換する操作を $ 0 $ 回以上繰り返して $ N $ を得ることが出来るものの個数を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースへの答えを出力せよ。

### Sample Explanation 1 例えば、 $ 2 $ 番目のテストケースについて、 $ x = 102 $ からはじめて $ x $ を $ x + f(x) $ に変換する操作を繰り返すと - $ 102 \to 104 \to 106 \to 108 \to 110 $ となり $ N=110 $ を得ることが出来ます。条件を満たす $ x $ は $ x=102,104,106,108,110 $ の $ 5 $ 個のみです。 ### Constraints - $ 1 \leq T \leq 2 \times 10^4 $ - $ 1 \leq N \leq 10^{18} $ - 入力される値は全て整数