Возведение в степень

Первокласснику Васе родители подарили на день рождения калькулятор. Вася быстро изучил все возможности своего нового калькулятора. Больше всего ему понравилась операция возведения в степень. Он был очень впечатлен тем, что даже если небольшое число возвести в степень с небольшим показателем, то результат может получиться очень большой.

Возводить в степень сам Вася пока не умеет, но очень хочет научиться. Для начала он решил научиться определять по числам $a$ и $b$, сколько цифр будет в десятичной записи числа $a^b$ ($a$ в степени $b$). Однако это у него не получилось, и он обратился за помощью к своему другу, второкласснику Роме. Рома --- большой любитель делать все наоборот. Он предложил Васе сначала научиться по числу $k$ находить числа $a$ и $b$, такие что число $a^b$ состоит из $k$ цифр в десятичной записи. Поскольку таких $a$ и $b$ может быть большое количество, Вася попытался научиться выяснять, сколько существует пар $(a, b)$, удовлетворяющих данному условию.

К сожалению, Васе не удалось и это, и теперь он просит о помощи Вас. Напишите программу, отвечающую на поставленную задачу.

Во входном файле задано единственное целое положительное число $k$ ($1 \le k \le 17$).

В выходной файл выведите количество различных пар $(a, b)$, таких что $a$ и $b$ --- целые положительные числа ($a > 1$), и число $a^b$ состоит из $k$ цифр в десятичной записи.