Consider the number of the form a ^ (a ^ (a ^ ...) 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 and 16 = 2 ^ (2 ^ 2) are numbairs. Number 1 is numbair too since 1 = 1 ^ 1. Find out how many numbairs are there between 1 and n inclusive.

Input

One integer n (1 ≤ n ≤ 109).

Output

Print the number of numbairs not exceeding n.