Số Hexa là số biểu diễn trong hệ đếm \(16\), trong đó quy ước \(10\) là \(A\), \(11\) là \(B\), \(12\) là \(C\), \(13\) là \(D\), \(14\) là \(E\) và \(15\) là \(F\). Chẳng hạn số tự nhiên \(6747\)=\(1 x 16^3 + 10 x 16^2 + 5 x 16^1 + 11 x 16^0\) nên biểu diễn thành số Hexa là \(1A5B\). Viết liên tiếp các số tự nhiên \(1, 2, 3, ...\) thành dãy sau khi đã biểu diễn chúng dưới dạng số Hexa, ta được một dãy vô hạn các chữ số Hexa như sau: \(123456789ABCDEF101112131415161718191A1B1C…\)

Yêu cầu: Cho trước một số nguyên dương \(N (0<N<=10^{12}),\) tìm chữ số thứ \(N\) trong dãy trên.

Dữ liệu: Gồm một dòng chứa số nguyên dương \(N\).

Kết quả: Ghi ra chữ số thứ \(N\) tìm được.

Ví dụ 1:

Input

10

Output

A

Ví dụ 2:

Input

16

Output

1

Ràng buộc:

• Có 30% số test ứng với 30% số điểm của bài có \(n<10^5\);
• Có 30% số test ứng với 30% số điểm của bài có \(10^5<n<=10^9\);
• Có 40% số test ứng với 40% số điểm của bài có \(n>10^9.\)