Số may mắn là số được định nghĩa theo quá trình sau:

• Bắt đầu với số nguyên dương \(x\) và tính tổng bình phương \(y\) các chữ số của \(x\).
• Sau đó tiếp tục tính tổng bình phương các chữ số của \(y\). Quá trình này lặp đi lặp lại cho đến khi thu được kết quả là \(1\) thì dừng hoặc quá trình sẽ kéo dài vô tận.
• Số mà quá trình tính này kết thúc bằng \(1\) gọi là số may mắn.

Những số may mắn đầu tiên là \(1, 7, 10, 13, 19, 23, 28, 31, 32, 44, \ldots\)

Cho số nguyên \(k\). Hãy tìm số may mắn thứ \(k\).

Input

• Chứa duy nhất số nguyên \(k\) \((1 \leq k \leq 10^{18})\).

Output

• Một số nguyên duy nhất là số may mắn thứ \(k\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(k \leq 10^6\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

10

44