Last Nonzero Digit

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given positive integer n, find its rightmost nonzero decimal digit, ignoring any trailing zeroes.

Input

One positive integer n.

Output

Print an integer digit from 1 to 9.

Subtasks

• Subtask 1 (20%): 1 <= n <= 99.
• Subtask 2 (30%): 1 <= n <= 100000.
• Subtask 3 (50%): 1 <= n <= 10^18.

Examples

Example 1

Input

10500

Output

5

Explanation

Discard 2 trailing zeroes: 10500 -> 1050 -> 105; the last digit is 5.

Example 2

Input

10

Output

1

Explanation

Removing the trailing zero from 10 leaves 1.