Salary

Time limit2sMemory limit1024 MB

Summary

Given k up to 10^18, find the k-th digit of the string formed by writing the cubes 1, 8, 27, 64, ... one after another.

Level: Medium6 of 10
Topics: Math, Binary search, Implementation
Solved: No attempts yet

Problem

Dima has just started a job. Since he is a very valuable employee, his salary grows not by the day but by the hour. More precisely, each month his salary in rubles equals the month number cubed. So he gets $1$ ruble in the first month, $8$ in the second, $27$ in the third, and so on.

Tax calculation

Tax laws are complicated. Recently the country where Dima works passed a new law. Under it, the percentage of tax an employee pays each month is computed as follows.

Write the salary for the first month, append the salary for the second month to its right, then the third, and so on, until the total number of digits in the written number is greater than $k$ .
The $k$ -th digit of the written number is the tax percentage.

Each organization has its own $k$ . Dima knows the value for his organization and wants to know what percentage of his salary he will pay as tax each month.

Input

The first line of the input file contains one integer $k$ ( $1 \le k \le 10^{18}$ ).

Output

Print to the output file one integer $x$ ( $0 \le x \le 9$ ), the required percentage.

Hint

For $k=7$ the written string is $182764125$ , and its seventh digit is $1$ .

Examples2

Example 1
Input
```
3
```
Expected output
```
2
```
Example 2
Input
```
7
```
Expected output
```
1
```