Числицы

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

Входные данные

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

Выходные данные

Вывести количество числиц, не превосходящих n.

Примеры