Сходові числа

Розглянемо числа вигляду a ^ (a ^ (a ^ ...), де a - натуральне число, яке в записі зустрічається два і більше разів, ^ - операція піднесення до степеня. Назвемо такі числа "Сходовими" (число + сходи). Наприклад 27 = 3 ^ 3 і 16 = 2 ^ (2 ^ 2) є сходовими числами. Число 1 є також сходовим числом, так як 1 = 1 ^ 1. А числа 2, 3, 5 не є сходовими числами, бо їх не можна подати у потрібному вигляді. Знайдіть кількість сходових чисел на проміжку від 1 до n включно.

Вхідні дані

Одне число n (1 ≤ n ≤ 10^9).

Вихідні дані

Вивести кількість сходових чисел, які не перевищують n.

Приклади