Cho số nguyên dương n.

Yêu cầu: Tìm số nguyên dương nhỏ nhất x sao cho tổng các chữ số của x bằng tổng các chữ số của n.

Ràng buộc: 1 ≤ n ≤ 10⁹.

Input

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

Output

Một dòng ghi giá trị x tìm được.

Ví dụ — Input

2019

Ví dụ — Output

39

Giải thích: Tổng chữ số của 2019 là 12; số nguyên dương nhỏ nhất có tổng chữ số bằng 12 là 39.