Description

字符串 $S$ 由 $S_1 S_2 \dots S_k$, $K$ 个字符串组成。其中 $S_i$ 由 $1$ 到 $i$ 的十六进制数字依次组成。

例如，$S_4$ = $1234$。 $S_16$ = $123456789ABCDEF10$。 $S$ 的前 $200$ 个字符如下：

112123123412345123456123456712345678123456789123456789A123456789AB123456789ABC123456789ABCD123456789ABCDE123456789ABCDEF123456789ABCDEF10123456789ABCDEF1011123456789ABCDEF101112123456789ABCDEF10111213

给定任意一个 $i$, 求字符串 $S$ 中第 $i$ 个字符是什么。 所以 $i=3$ 时，字符为 $2$, $i = 10$时，字符串为 $4$, $i=192$ 时，字符为 $F$ 。

Format

Input

有多组输入数据，每行包含一个位置 $i$ ， $1<=i<=2000000000$ 。

Output

对于每个给定的位置 $i$ ，输出该位置上的字符，对于 A~F 字符，请输出大写字母。

Samples

3
10
192  

2
4
F