Numbairs#7327

Numbairs

1 second

122.174 megabytes

Very easy

Consider the number of the form $a^{a^{a^{\dots}}}$ a^{a^{a^{\ldots}}} where $a$ is a positive integer that can appear in the notation twice or more, $^$ is power operation. Let us call such numbers numbairs (which stands for number + stairs). For instance $27 = 3^{3}$ 27 = 3^3 and $16 = 2^{2^{2}}$ 16 = 2^{2^2} are numbairs. Number $1$ is a numbair too since $1 = 1^{1}$ 1 = 1^1. Numbers $2$ , $3$ , $5$ are not numbairs because they cannot be represented in the required form. Find out how many numbairs there are between $1$ and $n$ inclusive.

Input

One integer $n$ ( $1 \leq n \leq 1 0^{9}$ 1 \leq n \leq 10^9).

Output

Print the number of numbairs not exceeding $n$ .

Examples

Example 1

Loading

a^{a^{a^{\dots}}}

27 = 3^{3}

16 = 2^{2^{2}}

1 = 1^{1}

1 \leq n \leq 1 0^{9}