Petriukas doesn’t like writing numbers, but he still needs to practice.
To help him train, his father gave him a challenge.
He must write down all numbers from 1 to N where no digit appears more than twice in any number.
Petriukas already reached the first number that could be skipped — number 111 — but he doesn’t know how many more numbers he actually needs to write.
Help Petriukas by calculating how many numbers from 1 to N have no digit repeated more than twice.
Input
A single natural number N (111 \le N \le 10^{18}).
Output
Print a single integer — the number of valid numbers Petriukas needs to write.
Example
| standard input | standard output |
|---|
| 123
| 122
|