Chữ số cuối không bằng 0 (Last Nonzero Digit)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho số nguyên dương $n$. Tìm chữ số khác 0 nằm xa nhất về bên phải trong biểu diễn thập phân của $n$. Các chữ số 0 ở cuối không làm thay đổi chữ số cần tìm.

Input

Một số nguyên dương $n$.

Output

Chữ số nguyên từ 1 đến 9.

Subtask

• Subtask 1 (20%): $1\le n\le99$.
• Subtask 2 (30%): $1\le n\le10^5$.
• Subtask 3 (50%): $1\le n\le10^{18}$.

Ví dụ

Ví dụ 1

Input

10500

Output

5

Giải thích

Chia 10500 cho 10 được 1050, tiếp tục được 105. Chữ số cuối của 105 là 5 nên in 5.

Ví dụ 2

Input

10

Output

1

Giải thích

10 có chữ số tận cùng là 0. Chia cho 10 được 1 và chữ số cần tìm là 1.