Problem 5C. 幸运数

题目描述

pzr 不喜欢 $6$，他认为，所有 不含 $6$ 的正整数 都是幸运数。

pzr 将所有幸运数（的十进制表示）排成一排，形成一个无限长的字符串 $s=1234578910111213141517\cdots$

给定 $k$，求 $s$ 的第 $k$ 个字符。

输入格式

仅一个正整数 $k$。

输出格式

仅一个 $0\sim 9$ 之间的数位，表示答案。

样例输入1

16

样例输出1

3

样例输入2

123457

样例输出3

9

样例输入3

1000000000000000

样例输出3

5

数据范围及约定

对于 $60\%$ 的数据，$1\le k\le 10^6$

对于所有数据，$1\le k \le 10^{15}$