Năm 1973, nhà Toán học Neil Sloan đưa ra khái niệm độ bền của một số nguyên không âm ~N~ như sau:

• Nếu ~N~ có một chữ số thì độ bền của ~N~ bằng 0.
• Nếu ~N~ có từ 2 chữ số trở lên thì độ bền của ~N~ bằng độ bền của số nguyên là tích các chữ số của ~N~ cộng 1.

Cho ~N~, tìm số bé hơn ~N~ có độ bền lớn nhất (~0 \leq N \leq 2.000.000.000~).

Input

Một dòng duy nhất chứa số nguyên dương ~N~.

Output

Một dòng gồm 2 số tương ứng là số nguyên thỏa yêu cầu đề bài và tổng độ bền, các số cách nhau bởi 1 khoảng trắng.

Sample Test

Input

100

Output

77 4

Giải thích:

Độ bền của 77 = Độ bền của 49 + 1 = Độ bền của 36 + 1 + 1 = Độ bền của 18 + 1 + 1 + 1 = Độ bền của 8 + 1 + 1 + 1 + 1 = 0 + 1 + 1 + 1 + 1 = 4