Any non-negative integer (including ~0~) is sorty if its digits are in a strictly increasing order, from most significant to least significant. In other words, for any digit, any other digit which has lower significance than it must have strictly greater value.

For example, ~167~ is sorty, since ~1 < 6~ and ~6 < 7~.

~429~ is not sorty, since ~4 > 2~.

~444~ is also not sorty, since the digits must be strictly ascending, meaning they cannot be the same.

Given some integer ~n~, output the number of sorty numbers in the range ~[0, n]~.

Input

A single integer is given, ~n~.

Output

Output a single integer, which is the number of sorty numbers less than or equal to ~n~.

Constraints

• ~0 < n \le 10^9~

Example 1

Input

12

Output

11

Explanation

The first ~11~ sorty numbers are: ~0, 1, 2, 3, 4, 5, 6, 7, 8, 9~ and ~12~.

Example 2

Input

244

Output

80

Example 3

Input

214

Output

74