Exponentiation

Time limit2sMemory limit1024 MB

Summary

Given k, count the pairs (a, b) with a at least 2 and b at least 1 such that a^b has exactly k decimal digits.

Level: Medium4 of 10
Topics: Math, Brute force
Solved: No attempts yet

Problem

Vasya's parents gave him a calculator for his birthday. He quickly learned everything it could do, and he liked the exponentiation operation the most. He was amazed that even a small number raised to a small power can give a very large result.

Vasya cannot compute powers by hand yet, but he wants to learn. First he tried to work out, for numbers $a$ and $b$ , how many digits the decimal form of $a^b$ has. That did not work, so he asked his friend Roma, a second grader, for help. Roma likes doing everything backwards. He suggested that Vasya first learn to find numbers $a$ and $b$ given a number $k$ , such that $a^b$ has exactly $k$ digits in decimal notation. There can be a large number of such $a$ and $b$ , so Vasya tried to learn how to count the pairs $(a, b)$ that satisfy this condition.

Vasya could not solve this either, so he now asks you for help. Write a program that solves this problem.

Input

The input file contains a single positive integer $k$ ( $1 \le k \le 17$ ).

Output

Print to the output file the number of distinct pairs $(a, b)$ such that $a$ and $b$ are positive integers, $a > 1$ , and $a^b$ has exactly $k$ digits in decimal notation.

Examples2

Example 1
Input
```
2
```
Expected output
```
102
```
Example 2
Input
```
3
```
Expected output
```
934
```