codeforces#P1157A. Reachable Numbers

Reachable Numbers

Description

Let's denote a function f(x)f(x) in such a way: we add 11 to xx, then, while there is at least one trailing zero in the resulting number, we remove that zero. For example,

  • f(599)=6f(599) = 6: 599+1=600606599 + 1 = 600 \rightarrow 60 \rightarrow 6;
  • f(7)=8f(7) = 8: 7+1=87 + 1 = 8;
  • f(9)=1f(9) = 1: 9+1=1019 + 1 = 10 \rightarrow 1;
  • f(10099)=101f(10099) = 101: 10099+1=10100101010110099 + 1 = 10100 \rightarrow 1010 \rightarrow 101.

We say that some number yy is reachable from xx if we can apply function ff to xx some (possibly zero) times so that we get yy as a result. For example, 102102 is reachable from 1009810098 because f(f(f(10098)))=f(f(10099))=f(101)=102f(f(f(10098))) = f(f(10099)) = f(101) = 102; and any number is reachable from itself.

You are given a number nn; your task is to count how many different numbers are reachable from nn.

The first line contains one integer nn (1n1091 \le n \le 10^9).

Print one integer: the number of different numbers that are reachable from nn.

Input

The first line contains one integer nn (1n1091 \le n \le 10^9).

Output

Print one integer: the number of different numbers that are reachable from nn.

Samples

输入数据 1

1098

输出数据 1

20

输入数据 2

10

输出数据 2

19

Note

The numbers that are reachable from 10981098 are:

1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,1098,10991, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 1098, 1099.