Competitions

# Numbairs

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 (1n109).

#### Output

Print the number of numbairs not exceeding n.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
5

Output example #1
2

Source 2014 ACM-ICPC Ukraine, 2nd Round Ukraine, September 13, Problem D