Strange Line

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

On Zenyk and Marichka’s farm, there are a lot of stallions. Each stallion has a tag on its neck with a single digit from 0 to 9.

Zenyk and Marichka want to line up the horses in a row.

We call a line of horses a decimal line for a non-negative integer \(m\) if the digits on the tags of the horses’ necks from left to right form the decimal representation of the number \(m\). In a decimal line, the first horse can have a tag with the digit 0 on its neck in only one case — if this is the line for \(m=0\).

We call a decimal line strange if the following conditions are met simultaneously:

• all horses in the line have different digits on their tags,

• the digits on the tags of the horses in the line form a palindrome, i.e., they read the same from left to right and from right to left.

For example, the decimal line 6 is strange because it reads the same in both directions, and no digit is repeated. The decimal line 123 is not strange because it reads differently from left to right (123) and from right to left (321). The decimal line 474 is not strange because the digit 4 is repeated twice in it.

For a given integer \(n\), count the number of integers \(0 \le m \le n\) for which the decimal line is strange.

Input

The single line contains the integer \(n\).

Output

Output an integer — the number of integers from \(0\) to \(n\) for which the decimal line is strange.

Constraints

\(1 \le n \le 10^9\).

Scoring consists of the following blocks:

• 1 point for each example from the statement,

• 18 points: \(n < 10\),

• 40 points: \(n \le 1000\),

• 40 points: no additional constraints.

You will receive the points for a block only if your solution passes all tests in that block.

Samples

Input (stdin) сopy	Output (stdout) сopy
4	5

Input (stdin) сopy	Output (stdout) сopy
14	10

Notes

In the first example, \(n=4\). For this example, there are five strange decimal lines: 0, 1, 2, 3, 4.