Вчера у Павла был день рождения, и на нем он с Андреем играл в следующую игру: Андрей старался угадать возраст Павла. Андрей знает, что возраст Павла является целым числом в промежутке от \textbf{1} до \textbf{n} включительно. Андрей может назвать любое число \textbf{x} между \textbf{1} и \textbf{n}, а Павел скажет ему значение наибольшего общего делителя \textbf{x} и его возраста. Рассмотрим один из возможных исходов игры для \textbf{n = 6}. Андрей называет \textbf{3}, Павел отвечает, что НОД \textbf{3} и его возраста, равен \textbf{1}. Значит возраст Павла не может быть ни \textbf{3}, ни \textbf{6}, но может равняться \textbf{1}, \textbf{2}, \textbf{4} или \textbf{5}. Андрей продолжает игру называя \textbf{2}, на что Павел отвечает \textbf{2}. Возраст Павла не может равняться \textbf{1} или \textbf{5}, остались только два варианта - \textbf{2} и \textbf{4}. Наконец, Андрей называет \textbf{4}, Павел отвечает \textbf{2}. Следовательно возраст Павла \textbf{2}, игра окончена. В приведенном примере Андрею понадобилось три попытки. Однако Павлу достаточно двух попыток при \textbf{n = 6}. Оптимальная стратегия Андрея следующая: сначала следует сказать \textbf{6}. Если Павел ответит \textbf{1}, тогда ответом будет \textbf{1} или \textbf{5}, который можно определить назвав \textbf{5}. Если Павел скажет \textbf{2}, то ответом будет \textbf{2} или \textbf{4}, и его можно найти назвав \textbf{4}. Если Павел скажет \textbf{3}, тогда ответом будет \textbf{3}. Если Павел скажет \textbf{6}, то ответ \textbf{6}. Найдите наименьшее количество попыток, достаточное Андрею в худшем случае найти ответ для заданного значения \textbf{n}. \InputFile Входные данные содержат одно целое число \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{10000}). \OutputFile Вывести одно целое число --- количество попыток, достаточное Андрею угадать возраст Павла в худшем случае.