Trong giờ toán học Minh được An đưa cho một con số với yêu cầu hãy biến đổi số đó thành số tối giản. An đưa ra quy tắc tìm số tối giản như sau: Tính tổng các chữ số của nó cho đến khi thu được số có một chữ số. Hãy giúp Minh lập trình giải bài toán trên.

Ví dụ: Cho số \(12\), ta có: \(12\) biến đổi \(1+2=3\). Vậy số tối giản của số \(12\) là \(3\).

Yêu cầu: Cho số nguyên dương \(N\). Em hãy lập trình tìm số tối giản của \(N\).

Input

• Một dòng duy nhất chứa số nguyên dương \(N\) \((N \le 10^9)\).

Output

• Một số duy nhất là số tối giản của \(N\).

Example

5432

5