Sau ngày thi thứ nhất, Minh rất vui vẻ vì mình làm bài rất tốt. Với động lực đó, Minh càng hăng say học tập. Hôm nay, Minh bắt tay vào nghiên cứu số Fibonaci. Sử dụng công thức tổng quát của dãy số Fibonaci:

~F_1 = F_2 = 1,~ ~F_n = F_{n-1} + F_{n-2}~ (~n \ge 3~)

Minh lần lượt tính các số của dãy số Fibonaci và viết chúng cạnh nhau từ trái qua phải tạo thành một dãy số vô hạn: 112358132134.... Minh có một câu hỏi: với dãy số vô hạn được tạo bằng cách trên, thì chữ số thứ ~K~ tính từ trái qua phải là chữ số nào. Bạn hãy lập trình giúp Minh trả lời câu hỏi trên.

Yêu cầu: Cho số tự nhiên ~K~, hãy tìm chữ số thứ ~K~ (tính từ trái qua phải) của dãy số vô hạn mà Minh tạo ra.

Dữ liệu

Gồm một dòng chứa một số tự nhiên ~K~ (~1 \le K \le 10^9~).

Kết quả

Gồm một dòng ghi chữ số thứ ~K~ của dãy số vô hạn mà Minh tạo ra.

Ví dụ

Ví dụ 1

CAU4.INP

1

CAU4.OUT

1

Ví dụ 2

CAU4.INP

11

CAU4.OUT

3