Gọi S là một tập các số thỏa mãn điều kiện sau: nếu gọi sum là tổng các chữ số của x thì luôn tồn tại số tự nhiên k sao cho có sumk = x. Cho một số n bất kì, các bạn hãy tìm chữ số x thuộc tập S sao cho |n – x| là nhỏ nhất. Nếu có nhiều số x cùng thỏa mãn in ra số x nhỏ nhất.
Dữ liệu vào
Gồm duy nhất một số nguyên dương n (n <= 1018)
Dữ liệu ra
Một số x thuộc tập S thỏa mãn điều kiện đã nêu.
Input
511
Output
512
Giải thích
Ta có (5+1+2)3 = 512. Có thể chứng minh được 512 là số tự nhiên gần 511 nhất và thỏa mãn các điều kiện yêu cầu.