P - LIS 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 7 点

問題文

正整数 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 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \leq T \leq 2 \times 10^4
  • 1 \leq N \leq 10^{18}
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

N

出力

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

入力例 1

6
7
110
1000000000000000000
567784738694904180
555056967895592095
942135357890920474

出力例 1

7
5
1000000000000000000
23644
22551
60795

例えば、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 個のみです。

Score : 7 points

Problem Statement

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.

Constraints

  • 1 \leq T \leq 2 \times 10^4
  • 1 \leq N \leq 10^{18}
  • All input values are integers

Input

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

Output

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

Sample Input 1

6
7
110
1000000000000000000
567784738694904180
555056967895592095
942135357890920474

Sample Output 1

7
5
1000000000000000000
23644
22551
60795

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.