H. Hexadecimal Digits of an Integral 

Time Limit: 8 seconds

Problem

Compute the n^th digit, in the hexadecimal expansion of the following expression.

In other words, if the expression is equal to n₁.n₂n₃...n_k... in hexadecimal. Given k, output n_k. Each digit is an element of {1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. For example, the hexadecimal expansion of 1/11 is 0.0F0F0F0F0F...

The Input

The input will consist of at most 50 lines with the value of k(k<1000001) on each line.

The Output

For each line of input, output the hexadecimal digit on a single line.

Sample Input

100
200

Sample Output

A
4

Problem setter: Josh Bao